在最坏的情况下,从已知列表创建二叉树的复杂度将是O(n2),但平均情况是O(n log n)。最坏情况和平均情况之间的差异取决于创建后树的平衡程度。如果maxDepth == n,则为最坏情况,如果maxDepth == log(n),则为最佳情况。在构建树之前知道maxDepth会给予许多有关创建树的运行时间的洞察力。
最大深度
是否有一种方法可以在O(n)时间内确定最大深度(或近似值)?我想不出一种方法来做到这一点。相反,我选择尝试找到初始列表的“排序程度”。
排序程度
在二叉树的最坏情况示例中,排序列表最终将功能上等同于链接列表。列表排序程度越高,二叉树的性能越差。我找不到任何可以给出列表“排序因子”的东西。我尝试过的算法适用于我所需的内容,但感觉不太“对”。
最大深度
是否有一种方法可以在O(n)时间内确定最大深度(或近似值)?我想不出一种方法来做到这一点。相反,我选择尝试找到初始列表的“排序程度”。
排序程度
在二叉树的最坏情况示例中,排序列表最终将功能上等同于链接列表。列表排序程度越高,二叉树的性能越差。我找不到任何可以给出列表“排序因子”的东西。我尝试过的算法适用于我所需的内容,但感觉不太“对”。
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;
}
*“right” - 这个算法并没有基于任何坚实的证据或概念。它是基于对数据进行模糊测试,以查看是否按半排序顺序排序为组的3。选择3是因为它比1和2都要大。
问题
有没有一种方法可以在O(n)时间内根据给定列表确定未来二叉树的最大深度(或近似值)?
“已排序性”是否是列表的可确定属性?它能否在O(n)时间内确定,还是需要更大的时间复杂度空间?
免责声明
我知道自平衡二叉树(红黑树,AVL),但是对于这个问题,它们不太有趣。它们与上述两个问题无关,而是解决了那两个问题的背景信息。