参考比较排序算法，决策树中叶子的最短可能深度是多少？
它会根据算法而改变吗？
问问题
7726 次
2 回答
8
绝对最好的情况发生在我们检查每个元素并看到数据已经排序时。
这将导致n-1比较，因此叶子的深度为n-1.
实际上，这种情况发生在插入排序中（否则就不是那么好）。
它会根据算法而改变吗？
绝对地。算法的最佳情况是一个很好的指标——具有 O(n log n) 最佳情况的最短深度将长于具有 O(n) 最佳情况的最短深度。
于 2013-10-29T15:39:11.520 回答
0
要查看这一点，请考虑 n 个节点的图，每个节点 i 代表 A[i]。如果我们比较 A[i] 和 A[j] 在从根.
Note that for k < n−1, this graph on {1, . . . , n} will not be connected. Hence we have
two components C1 and C2 and we know nothing about the relative order of array
elements indexed by C1 against elements indexed by C2. therefore there cannot be a
single permutation π that sorts all inputs passing these k tests - so π(到
于 2018-11-16T20:45:52.487 回答