在最坏的情况下,从已知列表创建二叉树将是O(n2),但是平均情况是O(n logn) . 最坏情况和平均情况之间的差异取决于树在创建后的不 balancer 程度 . 如果 maxDepth == n
,那么这是最糟糕的情况,如果 maxDepth == log(n)
那么这是最好的情况 . 在构建树之前了解 maxDepth
可以很好地了解创建树的运行时间 .
Max Depth
有没有办法在O(n)时间内确定最大深度(或近似值)?我想不出办法做到这一点 . 相反,我选择尝试找到初始列表的“已排序” .
Sorted-ness
在二叉树的最坏情况示例中,排序列表最终在功能上等同于链表 . 列表排序越多,二叉树的性能越差 . 我找不到任何可以给出列表的“排序因子”的东西 . 我试过的算法适用于我需要的东西,但感觉不对“*” .
public double sortFactor(int[] ar) {
//assume lists are larger than 10000 elements
int prevSum = ar[0] + ar[1] + ar[2];
int numIncreasing = 0;
for(int i=3; i < ar.length-3; i+=3) {
int sum = ar[i] + ar[i+1] + ar[2];
if (sum > prevSum) {
numIncreasing++;
}
prevSum = sum;
}
int totalSets = ar.length/3;
double sortFactor = (double) numIncreasing / (double) totalSets;
return sortFactor;
}
*“正确” - 此算法不基于任何基于实地的证据或概念 . 它基于模糊数据,以查看3个组是否按排序到半排序 . 选择3是因为它大于1和2 .
Questions
有没有办法在O(n)时间内根据给定列表确定未来二叉树的最大深度(或近似值)?
“sorted-ness”是列表的可确定属性吗?可以在O(n)时间内确定还是需要更大的时间复杂度空间?
Disclaimer
我知道自 balancer 二叉树(Red-Black,AVL),但出于这个问题的目的,它们是无趣的 . 它们与上述任何一个问题无关,而是与这两个问题的起源背景信息有关 .
1 回答
它当然可以在时间O(n log n)内完成 . 我对线性决策树模型中的O(n)持怀疑态度,但我没有任何证据 .
保留从现有键之间的间隔到新节点插入深度的有序映射 . 对于每个点的顺序,找到它的间隔并在深度加1分成两个 .
在
3, 1, 4, 5, 9
上执行示例:获得深度
4
(包括空节点)的答案 . 这是树(*
表示null):