在代码片段中查找递归函数
在代码片段中查找递归函数
提问于 2021-03-23 13:57:29
我应该找到这段代码的递归函数，但我真的很困惑我所做的是不是正确的。我会用-线条来展示我的思维方式。
假设树是平衡的。
// compute tree height (longest root-to-leaf path)
int height(TreeNode* root) {
if (root == NULL) return 0; **-------- C**
else {
// Find height of left subtree, height of right subtree
//Use results to determine height of tree
return 1 + max(height(root->left), height(root->right)); **---- n/2**
}
}我相信这个代码的递归函数是T(n) =c+ n/2，但是我觉得我好像遗漏了什么。
回答 1
Stack Overflow用户
发布于 2021-03-23 14:13:34
递归关系为：
T(n) = 2T(n/2) + 1
在任何级别上，都会有该级别的一些操作，还有2个对左子树和右子树的调用。
我们可以从这里推导出时间复杂度：
T(n) = 2T(n/2) + 1
= 2 [2(T(n/4) + 1] + 1
= 4T(n/4) + 1 + 1= 4T(n/4) + 2
= 4 [2T(n/8) + 1] + 2
= 8T(n/8) + 3
= 2kT(n/2k) + n ·保持n= 1，2，…设n= 2k，则k=log2 n
= T(1) + n log(n) 因此，时间复杂度将是nlog(n)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/66757980
复制相关文章
相似问题
腾讯云开发者
