为什么递归树的时间复杂度等于叶子节点数而不是总节点数？
为什么递归树的时间复杂度等于叶子节点数而不是总节点数？
提问于 2021-05-04 22:31:39
下面是简单递归函数的时间和空间复杂度：
它的时间复杂度为O(2^n)，这是叶子节点的数量。但是在树的每个节点上都有一个函数调用。为什么时间复杂度等于叶子节点数，而不是总节点数？
回答 2
Stack Overflow用户
发布于 2021-05-04 23:27:12
如果只计算树叶或所有节点，则不会改变复杂性。
所有非离开节点都是2^n-1。
O(2^n + 2^n-1) = O(2^n)。
Stack Overflow用户
发布于 2021-05-05 16:14:29
这棵树有5和16个叶节点的深度，上次我检查2^5是32而不是16...它是2^n，因为有2^(n -1 ) + 2^(n-2) + ... + 2^1个节点恰好进行了2^n-1次调用，丢弃了-1得到的O(2^n)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/67386811
复制相关文章
相似问题
腾讯云开发者
