BST遍历分解复杂度

Question

我在Python中有如下BST遍历函数：

def print_tree(tree):
    if tree == None:
        return
    else:
        print tree.value
        print_tree(tree.left)
        print_tree(tree.right)

最坏情况下的时间复杂度是O(n)，但我很难证明它。我正在尝试使用常量 c 对其进行分解，这就是我所拥有的：

T(n) = 2T(n-1) + cn

其中 T(n) 用于递归调用，cn 用于打印语句。但这似乎并不正确。

Answer 1

只是展开递归关系：

T(1) = c*n
T(2) = 3*c*n
T(3) = 7*c*n
T(4) = 15*c*n
...

如您所见，您永远不会得到 n 中非线性的项。

直觉上，复杂度是线性的，因为每个节点的工作量是恒定的，而且访问一个节点的次数不会超过一次。

如果树是平衡的，则递归关系变为

T(n) = 2T(n/2) + cn

并且可以使用 master theorem（案例 1）给出 O(n).

来解决

Answer 2

递归关系应该是

T(n) = 2T(n/2) + cn

然后从这个answer 你可以解决你的递归关系。假设 cn = Θ(1)

T(n)=2T(n/2)+Θ(1)
     =2T(n/2)+k
     =2{2T(n/4)+k)+k
     =4T(n/4)+3k
     =...
     =n.T(1)+(n-1)k
     =n.k+(n-1)k
     =2nk-k
     =O(n).

BST遍历分解复杂度

break-down complexity of BST traversal

python

recursion

big-o

time-complexity