算法分析基本概念

第 2 次迭代： n 2 个 2 元素的子序列被两两合并，
每次合并需要 2~3 次比较
第 3 次迭代： n 4 个 4 元素的子序列被两两合并，
每次合并需要 4~7 次比较
归纳起来，一般地：
第 j 次迭代：大小为 2 j1 的子序列被两两合并， n
合并操作共有 2 j 次，
每次合并需要 2 j1 ~ 2 j 1次比较
1
1.3.1 BINARYSEARCH 时间复杂度分析
为了找到最大比较次数，我们假定 x ≥ A[n] .
对算法 1.2 进行分析： 因为每次 while 循环迭代中进行了一次三向比较 所以，求得了 while 循环迭代的最大次数，也即是求出了最 大比较次数。
而最后一次 while 循环，并且对应于最大的循环次数的情况 是，当前的工作数组 A 中只剩下 1 个元素了。
剩余元素个数小于等于 1 个子段长度）。如果剩余元素个数 k
满足： 2 j1 k 2 j （即是说，剩余元素个数大于 1 个子段
长度），则将剩余元素合并成长度为 k 的排序序列。
1.7.1 BOTTOMUPSORT 算法分析： 我们这里讨论的是当 n 为 2 的幂这种特殊情况下，算法执行 的元素比较次数。
即：
1313 1 2 n 2 7 14
1 所以 c1 可以取为 14 。
通过取
c1
1 14
，c2
1 2
，n0
7
，证明了
1 2
n2
3n
(n2 )
。
14
当然，还存在其他的对常量的选择，
重要的是必须存在某些选择。
这些常量依赖于具体的函数
1 2
n2
3n
一个属于 (n2 ) 的另一个不同的函数，通常就要选择不同的
我们应该对上式进行更简单化的抽象。
我们其实真正关注的是 rate of growth 或 order of growth of running time
我们其实真正关注的是运行时间增长率或运行时间增长的 阶。
所以，可以只考虑上式的首项，即 an2
因为低阶项在 n 变大的时候变得相对来说不重要了。
我们还可以忽略掉首项常系数，因为对于大规模的输入来 说，常数因子相对于增长的阶在决定计算效率上不是那么重 要。
5
迭代。如果剩余 3 个元素，则将前 2 个元素和第 3 个元素合 并成一个 3 元素排序子序列。
n 第 j 次迭代：合并 2 j 个连续的且成对的大小为 2 j1 的子序
n 列对，得到长度为 2 j 的 2 j 个排序子序列。如果剩余元素 个数 k 满足：1 k 2 j1 ，则直接进入下一轮迭代（即是说，
分析剩余元素个数与循环迭代次数之间的关系： 第 1 次迭代时：剩余元素个数 = n
n 第 2 次迭代时：剩余元素个数 = 2
第 3 次迭代时：剩余元素个数 = n 2 2 n 4
第 j 次迭代时：剩余元素个数 = n 2 j1
搜索 x 的最大循环次数是满足条件 n 2 j1 1时的 j 值。 根据底函数的定义（P.45）， n 2 j1 1表示：
BOTTOMUPSORT 算法思想：
n
n
第 1 次迭代：合并 2 对连续元素，得到长度为 2 的 2 个
排序子序列。如果剩余 1 个元素，则直接进入下一 2 元素对，得到长度为 4 的 4
个排序子序列。如果剩余 1 或 2 个元素，则直接进入下一轮
参见教材 P.5
2
1.6 插入排序 观察结论 1.4 元素赋值次数等于元素比较次数加上 n-1(此结 论不对，可以举一个简单的反例说明) 如：[2, 1]
关于 INSERTIONSORT 中元素赋值次数和比较次数之间关 系的分析：
Step 4. while (j>0) and ( A[ j] x )
当算法每次的 for 循环内部的 while 循环，都是因为 step.4
中的条件 A[ j] x 不满足跳出时，
在每次的 for 循环内部，这次 for 循环所执行的赋值次数=
1 (step2) (这次 for 循环执行的比较次数-1)(step5) + 1
(step8) 所以，总元素赋值次数 = n-1 + 总元素比较次数
一个算法运行时间的增长率给出了对这个算法效率的一个 简单刻画，使我们能够比较两个算法的相对性能。
MERGESORT 最坏情形下运行时间 (n log n) INSERTIONSORT 最坏情形下运行时间 (n2 )
只要输入规模 n 变得足够大，MERGESORT 肯定是更优的。
尽管我们有时候可以明确地知道某个算法确切的运行时间， 但是通常来说，不值得耗费那么多精力去计算它。 对于足够大的输入规模，常数因子和低阶项就不那么重要 了，起主导作用的是运行时间增长率。
1.8 时间复杂性 1.8.1 增长的阶
n(n 1) INSERTIONSORT 最坏情形下运行时间是 2
我们使用一些简单化的抽象符号来使对 INSERTIONSORT 的分析变得简单。
首先，使用常数符号 ci 来替换掉每一项前面的系数。
9
现在最坏情形下运行时间： an2 bn c
然后，我们发现即便是这样的式子仍然给我们提供了过多的 过于详细的信息。
常数了。
证明 6n3 (n2 )
15
证明 6n3 (n2 ) 假设存在正常数 c2 和自然数 n0 ， 使得 6n3 c2n2 对于所有的 n n0 成立 n c2
6
上式不可能对于任意大的 n 都成立。从而证明了该命题。
任意的平方函数 f (n) an2 bn c ，其中 a,b,c 是常数， a 0 ， f (n) (n2)
（1）如果 a ≤ b 且 b ≤ a，则 a=b (反对称性) （2）如果 a ≤ b 且 b ≤ c，则 a ≤ c (传递性) （3）a ≤ b 或 b ≤ a（完全性） （关系的完全性可以如下这样描述：对于集合中的任何一对 元素，在这个关系下都是相互可比较的。） 则称≤为 X 上的一个全序关系，且称 (X, ≤) 为全序集。 例如：自然数集、整数集、实数集在通常的大小序下是全序 的。
(g(n)) 的定义要求每一个 f (n) (g(n)) 是渐近非负的， 也就是说，当 n 变得足够大时， f (n) 是非负的。 所以函数 g(n) 自身也必须是渐近非负的，否则 (g(n)) 就
是空集。
所以我们假定所有使用 符号的函数都是渐近非负的。
对于这一章中定义的其他渐近性符号，这一假设仍然成立。
第 j 次迭代总的元素比较次数：
(
n 2j
)2
j
1
~
(
n 2j
)(2
j
1)
外部 while 循环执行了 k log n 次，
7
即： j :1 ~ log n
所以，总的元素比较次数最少为：
k
j 1
(
n 2j
)2
j
1
kn j1 2
kn 2
nlog n 2
总的元素比较次数最多为：
k
j 1
(
n 2j
首先，外部的 while 循环执行 log n 次，
可以解释为排序树除树根以外每层执行一次。
因为 n 为 2 的幂，所以，第 8 步中的 MERGE 永远不执行。
先回忆一下，MERGE 算法的元素比较次数在 n1 到 n 1之间
6
（ n1 n2 ， n1 n2 n ） 第 1 次迭代： n 2 次比较
Step 4. while (j>0) and ( A[ j] x )
当算法每次的 for 循环内部的 while 循环，都是因为 step.4 中的条件 j>0 不满足跳出时， 在每次的 for 循环内部，这次 for 循环所执行的赋值次数=
1 (step2) (这次 for 循环执行的比较次数)(step5) + 1 (step8)
11
当我们只考虑输入规模充分大时运行时间增长的阶，我们实 际上是在研究算法的渐近性效率。
也就是说，我们关心的是当输入的规模无限增长，在某一个 限制下，算法的运行时间怎样随着输入规模的增长而增长。
通常来说，一个渐近性意义下效率较高的算法在大部分情况 下是一个较优的选择，除了对于非常小的输入规模例外。
d
一般地说，对于任意多项式 p(n) aini ，其中 ai 是常数， i0
ad 0 ，都有 p(n) (nd ) 。
因为任何常数都是 0 次多项式，因此我们把常数都表示为
16
(n0 ) 或 (1) 。
我们会经常使用 (1) 来表示一个常数，或者关于某些变量是
常函数。
1.8.2 O 符号 符号渐近性地界定了一个函数的上界和下界。当我们只有 一个渐近性的上界时，使用 O 符号。
*渐近性标识
符号
定义 1.4 P.16
一个函数 f (n) 属于 (g(n)) 集合，如果存在正常数 c1 ，c2 ， 使 得 对 于 足 够 大 的 n, f (n) 可 以 被 夹 在 c1(g(n)) 和 c2 (g(n)) 之间。
因为 (g(n)) 是一个集合，我们可以写 f (n) (g(n)) 来表 示 f (n) 是 (g(n)) 集合的， 也可以写 f (n) (g(n)) 表达相同的意思。
4
Step 8: 处理剩余元素： If (i+s<n) 即表示：s<n-i<t 即表示：剩余元素个数大于 1 个子段长度 所以：MERGE(A, i+1, i+s, n) 否则 i+s≥n 即表示：n-i≤s 即：剩余元素个数小于等于 1 个子段长度 所以：不作处理，直接进入下一轮迭代
对外层 while 循环判断语句：while t<n 的解释为： 判断 BOTTOMUPSORT 是否达到了排序树的最顶层。 t: 两段子序列的总长 所以，如果 t≥n 条件满足，则表示整个排序过程已完成。 算法完成了对整个数组 A 所有元素的排序。