文章/答案/技术大牛

发布

问BST遍历的分解复杂度
EN

Stack Overflow用户

提问于 2015-01-26 05:33:04

回答 2查看 140关注 0票数 1

我在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用于打印语句。但这似乎是不正确的。

time-complexity

python

recursion

big-o

回答 2

Stack Overflow用户

回答已采纳

发布于 2015-01-26 05:55:16

递归关系应该是

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

然后，从这个回答，你可以解决你的递归关系。假设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).

票数 2

Stack Overflow用户

发布于 2015-01-26 05:53:06

只需扩展重复关系：

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

并且可以用主定理 (例1)给出O(n)进行求解。

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/28145207

复制

相似问题

问BST遍历的分解复杂度
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问BST遍历的分解复杂度EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问BST遍历的分解复杂度
EN