MIT 6006 Lecture 7——计数排序，基数排序，排序的时间复杂度下界

AVL树——一种平衡的BST

课程内容

比较模型
时间复杂度下界
- 搜索：$\Omega(\lg n)$
- 排序：$\Omega(n\lg n)$
$O(n)$时间复杂度的排序
- 计数排序
- 基数排序

比较模型

定义

所有输入对象均为黑盒（抽象数据结构）
唯一允许的操作是比较操作（$<,\le,>,\ge,=$）
时间损耗只和比较操作的次数有关

决策树

任何的比较操作，实际上都可以视为一棵树，这棵树由可能的路径和结果构成。例如，二分查找可以被视为一颗二分查找树。下面给出了一个二分查找的过程，在长度$n=3$的数组里进行二分查找：

算法和树的对应关系如下：

决策树	算法
内部节点	二分决策（比较）
叶节点	结果
根到叶的路径	一次算法的执行
路径长度	算法的执行时间
树高	最坏执行时间

时间复杂度下界

搜索的时间复杂度下界

在$n$个经过处理（排序或其他操作）的对象中，根据比较模型找到一个指定的目标，最坏情况下时间复杂度下界为$\Omega(\lg n)$。

证明

首先，我们的决策树是一个二叉树，同时，这棵树至少有$n$个节点，每个节点对应一个解
所以树的高度$h\ge \lg n$，证明完毕

排序的时间复杂度下界

在搜索算法中，我们证明了$\Omega = \lg n$，即从$n$个对象中找到一个解的时间复杂度下界为$\lg n$，那么直观来看，如果我们要排序，就是从$n$个元素中找到$n$个解，这$n$个解分别为第一大元素、第二大元素、…、第$n$大元素，所以时间复杂度应为$n\lg n$。

证明

首先，对于这个排序问题，我们的决策树依旧是一个二叉树，所以我们要看一下这个树有多少个节点。对于排序问题，我们的一个节点也是一个解，这个解是一个排序序列，例如：

$A[5]\le A[7]\le A[10]\le A[2]\le...\le A[3]$

那么有多少个节点呢，根据排列组合，所有可能的情况为$A_n^n=n!$（$n$ factorial），则树高$h$满足

$h\ge \lg (n!)$

我们现在要证明$\lg(n!)\ge n\lg n$，证明过程如下：

$\begin{equation} \begin{aligned} \lg(n!)&=\lg(n(n-1)(n-2)...(2)(1)) \\ &=\lg(n)+\lg(n-1)+...+\lg(2)+\lg(1) \\ &\ge \sum_{i=n/2}^{n}\lg(i) \\ &\ge \sum_{i=n/2}^{n}\lg \frac{n}{2} \\ &=\sum_{i=n/2}^{n}(\lg n-1) \\ &=\frac{n}{2}(\lg n-1) \\ &=\Omega(n\lg n) \end{aligned} \end{equation}$

线性时间排序

假设我们的待排序的对象是整数，那么我们可以制造出一些整数排序的结果，我们先进行一些假设：

假设key是整数，且$key\in{0,1,2,…,k-1}$，同时一个key的长度小于计算机的一个字
不止可以进行比较操作，还可以进行别的操作
对于$k$，可以在$O(n)$时间复杂度下进行排序

目前来说，最好的排序算法能够达到的时间复杂度为$O(n\sqrt{(\lg n\lg n)})$

计数排序

配置一个计数器，然后遍历数组，每遇到一个元素，就将对应的$key$所在的位置+1，然后遍历计数器，进行排序。计数排序中一个比较重要的问题是考虑排序的稳定性，如果我们要保证相同元素排序后位次不变，那么可以使用如下算法：

L = array of k empty lists      O(k)
for i in range(n):              O(n)
    L[key(A[j])].append(A[j])   O(1)
output = []
for i in range(k)               O(n+k)
    output.extend(L[i])         O(|li|)

所以计数排序的时间复杂度为$O(n+k)$，如果$k$很大，那么性能很差。