求二叉树最小值的时间复杂度
求二叉树最小值的时间复杂度
提问于 2015-03-20 07:49:25
我编写了一个递归函数来查找二叉树的最小值(假设它是无序的)。
代码如下所示。
//assume node values are positive int.
int minValue (Node n) {
if(n == null) return 0;
leftmin = minValue(n.left);
rightmin = minValue(n.right);
return min(n.data, leftmin, rightmin);
}
int min (int a, int b, int c) {
int min = 0;
if(b != 0 && c != 0) {
if(a<=b) min =a;
else min =b;
if(min<=c) return min;
else return c;
}
if(b==0) {
if(a<=c) return a;
else return c;
}
if(c==0) {
if(a<=b) return a;
else return b;
}
}我凭直觉猜测minValue函数的时间复杂度为O(n)。
这是正确的吗？谁能给出minValue函数时间复杂度的形式证明？
回答 2
Stack Overflow用户
发布于 2015-03-20 08:24:43
假设你的二叉树是无序的，那么你的搜索算法将有O(N)的运行时间，所以你的直觉是正确的。使用O(N)的原因是，平均而言，您必须搜索树中一半的节点才能找到输入。但这假设树是完全无序的。
对于排序的和平衡二叉树，搜索将采用O(logN)。这样做的原因是，搜索将永远只需沿树向下遍历一条路径。具有N个节点的平衡树的高度将为log(N)，这解释了搜索的复杂性。以下面的树为例：
5
/ \
3 7
/ \ / \
1 4 6 8树中有8个节点(实际上是7个)，但高度仅为log(8) = 2。您可以说服自己，只需遍历此树一次即可找到值，否则会失败。
请注意，对于不平衡的二叉树，这些复杂性可能不适用。
Stack Overflow用户
发布于 2015-03-20 08:42:36
比较的次数是n-1。证明是old chestnut，通常用于说明在一场一次淘汰网球比赛中需要多少场比赛的问题。每次比较都会从考虑中删除一个数字，因此如果树中最初有n个数字，则需要n-1个比较才能将其减少到1。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/29157030
复制相关文章
相似问题
腾讯云开发者
