python - 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(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).