cn,其中c是一个正数,则有 T(n)= (4.2.1) 2T(n/2)+Cnn>1 其中,a是一个常数。若n是2的方幂:n=2,直接推导可得 T(n)=2(27(n/4)+cn/2)+cmn 47(n/4)+2cn 2 T(1)+kcn an +cn log n 对于一般的整数n,我们可以假定24<n≤2,于是T(m)≤T(2),得 以比较为基础的排序时间的下界 类似于估计搜索算法的时间下界,我们也可以用树来模拟排序算法,在此我 们考虑最坏情况下的时间下限,并假定数组中的元素互不相同。在树的内部顶点 上,算法执行一次比较,并根据比较的结果移向它的某一个孩子。由于每两个元 素A[i]和A[j]的比较只有两种可能:A[i]<A[j或A[j<A[i],所以这颗树是二 叉树。当A[i]<A[j时进入左分支,当A[j<A[i进入右分支。各个外部顶点(叶 顶点)表示算法终止。从根到外顶点的每一条路径与一种唯一的排列相对应。由 于n个不同元素的不同排列共有n!个,因此比较树至多有n!个外部顶点(参 看文档“排序比较树”)。直接观察可知,由根到外顶点路径即描述了该外顶点所 代表的排列生成过程,路径的长度即是经历的比较次数。因此,比较树中最长路 径的长度(其是比较树的高)即是算法在最坏情况下所做的比较次数。要求出所 有以比较为基础的排序算法在最坏情况的时间下界,只需求出这些算法所对应的 比较树的最小高度。如果比较树的高是k,则该二叉树的外顶点至多是2k个。于 是,最坏情况下的最少比较次数T(m)满足川≤2(。注意到 n2m(n-1)…(n/2D≥ 因而 T(n)>(n/2-1log(n/2)=O(nlog n) 从上式看出,归并排序是时间复杂性级别最低的排序算法(以比较为基础)cn，其中 c 是一个正数，则有    + > = = 2 ( / 2) 1 1 ( ) T n cn n a n T n (4.2.1) 其中，a 是一个常数。若n是2 的方幂： k n = 2 ，直接推导可得 an cn n T kcn T n cn T n T n cn cn k log 2 (1) 4 ( / 4) 2 ( ) 2(2 ( / 4) / 2) = + = + = + = + + LL 对于一般的整数 n，我们可以假定 1 2 2 + < ≤ k k n ，于是 ( ) (2 ) +1 ≤ k T n T ，得 T(n) = O(n log n) 。 z 以比较为基础的排序时间的下界 类似于估计搜索算法的时间下界，我们也可以用树来模拟排序算法，在此我 们考虑最坏情况下的时间下限，并假定数组中的元素互不相同。在树的内部顶点 上，算法执行一次比较，并根据比较的结果移向它的某一个孩子。由于每两个元 素 A[i]和 A[j]的比较只有两种可能：A[i]<A[j]或 A[j]<A[i]，所以这颗树是二 叉树。当 A[i]<A[j]时进入左分支，当 A[j]<A[i]进入右分支。各个外部顶点（叶 顶点）表示算法终止。从根到外顶点的每一条路径与一种唯一的排列相对应。由 于 n 个不同元素的不同排列共有 n！个，因此比较树至多有 n！个外部顶点（参 看文档“排序比较树”）。直接观察可知，由根到外顶点路径即描述了该外顶点所 代表的排列生成过程，路径的长度即是经历的比较次数。因此，比较树中最长路 径的长度（其是比较树的高）即是算法在最坏情况下所做的比较次数。要求出所 有以比较为基础的排序算法在最坏情况的时间下界，只需求出这些算法所对应的 比较树的最小高度。如果比较树的高是 k，则该二叉树的外顶点至多是 k 2 个。于 是，最坏情况下的最少比较次数 T(n)满足 ( ) ! 2T n n ≤ 。注意到   / 2 1 ! ( 1) ( / 2 ) ( / 2) − ≥ − ≥ n n n n L n n 因而 T(n) ≥ (n / 2 −1)log(n / 2) = Θ(n log n) 从上式看出，归并排序是时间复杂性级别最低的排序算法（以比较为基础）