CS161 Lecture 5

CS161

Heap Sort和Merge Sort所能达到的复杂度都是O(nlogn)级别的，这个算法还有可提升的空间吗？有什么可以使它更改进吗？在当前的逻辑中，被允许的运算有：

• 以对为单位的比较
• 移动元素到某位置

这样简单的运算就注定它只能是这个级别的。
一个更好的算法必然要求其他的运算，如：

• 算术运算（arithmetic operation）
• 列表索引（array indexing）

就如同Hash Table一样。
在输入的size足够小时，数字的比较可以由if-else逻辑穷举得到。无需循环，无需递归。

def sort3(a,b,c):
    if a<b:
        if b<c:
            return [a,b,c]
        elif a<c:
            return [a,c,b]
        else:
            return [c,a,b]
    else:
        if a<c:
            return [b,a,c]
        elif b<c:
            return [b,c,a]
        else:
            return [c,b,a]

从这个比较序列中可以画出一个比较树(Comparision Tree)
[img]
最差情况下要比较三次，平均比较$2\frac{2}{3}$次。
比较树是对if-then-else逻辑的一个速记方式。
可以被理解成是一个具有以下特征的二叉树：

• 在比较的元素
• 左/右子树
• 输出output

然后这个比较树的最长路径就是最差情况比较次数，平均路径长度就是平均比较次数。

The Lower Bound

如果排序结果正确的话，在比较树没有两个叶节点是重复的。共有n!个叶节点。
然而一个高度为h的二叉树应该有$2^h$个叶节点。所以n!向上取整到最近的$2^k$则k为得出的最差比较次数的最小可能。

Stirlings Approximition

结论：所有的比较排序至少需要$n\log_{2} n-1.44n$次比较，所以所有两两比较的排序最低是O($n \log n$)复杂度。