第1章 算法分析的基本概念和方法
内容提要
一、算法及其特性
  二、算法的时间空间复杂度
  三、算法分析(Algorithm Analysis)
1.分析算法时间复杂度的基本步骤
2.算法时间复杂度的有关概念
3.分析、求解算法复杂度的方法
  四、最优算法(optimal algorithm)
知识要点
算法分析的概念
复杂度渐近表示的记号：O, ,
平均时间复杂度，最坏时间复杂度，最好时间复杂度
最优算法
分析算法复杂度的基本方法
分析算法时间复杂度的步骤
基本运算执行频数的统计方法
数学知识：求和公式、定积分近似求和、递归方程的求解
学习要求
掌握算法复杂度的基本概念
熟悉算法复杂度分析的基本方法
1.1．算法及其特性
一、 算法(algorithm)    
算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。
二、算法的五个特性
确定性
能行性
有穷性
输入
输出
1.1．算法及其特性
衡量算法性能一般有下面几个标准：
确定性
易读性
健壮性
算法的时间和空间性能：高效率和低存储空间
    
本课程中主要讨论算法的时间和空间性能，并以此作为衡量算法性能的重要标准，而且主要侧重于时间方面。
三、衡量算法性能的标准
1.2. 算法的时间空间复杂度
算法的时间复杂度：在算法运行期间所花费的时间。
通常用渐进形式表示。比如，T(n)= O (n2)、 (n2) 或 (n2)
一、算法的时间复杂度(Time Complexity)
1.2. 算法的时间空间复杂度
算法的空间复杂度：在算法运行期间所需要的内存空间，通常指除开容纳输入数据之外的附加空间（auxiliary space, or work space）。
通常用渐进形式表示。比如，S(n)= O(n2)、(n2)或 (n2)
二、算法的空间复杂度(Space Complexity)
1.2. 算法的时间空间复杂度
算法分析是指对于计算机算法的时间和空间复杂度进行定量的分析。为了确切起见，假定执行算法的计算机是满足如下条件的“通用型”计算机：
顺序处理机：每次执行程序中的一条指令；
RAM足够大；
在固定的时间内可把一个数从一个单元取出或者存入。

    下面将学习算法分析的主要内容：
分析算法时间复杂度的基本步骤
算法时间复杂度的有关概念
分析、求解算法复杂度的数学知识
三、 算法分析 (Algorithm Analysis)
1.3. 分析复杂度的基本步骤
对算法的分析必须脱离具体的计算机结构和程序设计语言。因此，比较两个算法的好坏，看其中所需的运算时间的长短是由算法所需的运算次数决定的。任何一个算法都可能有几种运算，因此，我们抓住其中影响算法运行时间最大的运算作为基本运算。如在一个字表中寻找Z的问题，把Z和表中元素的比较作为基本运算。两个实数矩阵相乘的问题中，则把两个实数相乘作为基本运算。
一、选取一种运算作为基本运算(basic operation)
1.3. 分析复杂度的基本步骤
一个计算步骤，如果其时间耗费总是不超过某个常量，而与输入和算法无关，则称之为元运算。
元运算(elementary operation)
常见的元运算
算术运算：加、减、乘、除；
比较和逻辑运算；
赋值运算，包括指针赋值（比如，在遍历表或树时的指针赋值）；等等。
1.3. 分析复杂度的基本步骤
同一个问题对不同的输入，基本运算的次数亦可能不同。因此，我们引进问题大小（即规模，size）的概念。例如，在一个姓名表中寻找给定的Z的问题，问题的大小可用表中姓名的数目表示。对于两个实数矩阵相乘的问题，其大小可用矩阵的阶来表示。而对于遍历一棵二叉树的问题，其大小是用树中结点数来表示等等。这样，一个算法的基本运算的次数就可用问题的大小n的函数f(n)来表示。
二、表示出在算法运行期间基本运算执行的总频数
1.3. 分析复杂度的基本步骤
在一个算法中，出现的频数最高（在相差一个常数因子的意义上）的元运算称为基本元算。
基本运算(basic operation)
常见的基本运算
当分析查找和排序的算法时，如果元素的比较是元运算，则可作为基本运算；
在矩阵乘法的算法中，数的乘法可作为基本运算；
当遍历链表时，给指针赋值或者更新指针的操作可作为基本运算；
在图的遍历中，可以将访问节点的操作为基本运算；等等。
1.3. 分析复杂度的基本步骤
在实际中精确地求一个算法的基本运算次数f(n)等于多少，往往不容易，甚至有时根本不可能，有些即使求出结果很长，很繁琐，不易比较，需要简化。这时候我们可以不精确地估计f(n)。此外，我们分析算法的时间目的主要在于，能区分不同算法的优劣，在n很小时候，差别不大，随着n的逐渐增大，差别越来越大，是个极限行为。基于上述原因，引进下面渐近表示的方法。复杂度渐近表示可以将简洁地表示出复杂度的数量级别。
三 、渐近时间复杂度(asymptotic time complexity)
1.3. 分析复杂度的基本步骤
设f(n)和g(n)均是从自然数集到非负实数集上的函数。如果存在常数c>0和一个自然数n0，使得对于任意的n≥n0 ，均有        f(n)≤cg(n),则f(n)=O(g(n))。
含义：阶至多为g(n)的函数，即上限。
读法： O(g(n))读作“大Oh g(n)”。
1. O-记号
1.3. 分析复杂度的基本步骤
设f(n)和g(n)均是从自然数集到非负实数集上的函数。如果存在常数c>0和一个自然数n0，使得对于任意的n≥n0 ，均有        f(n)≥cg(n),则，f(n)= (g(n))。 
含义： 阶至少为g(n)的函数，即下限。
读法： (g(n))读作“omega g(n)”。
2. -记号
1.3. 分析复杂度的基本步骤
设f(n)和g(n)均是从自然数集到非负实数集上的函数。如果存在一个自然数n0和两个正常数c1，c2，使得对于任意的n≥n0 ，均有        c1g(n)≤f(n)≤c2g(n),则，f(n)= (g(n))。
含义： 阶恰好为g(n)的函数。
读法： (g(n))读作“theta g(n)”。
3. -记号
1.3. 分析复杂度的基本步骤
[例1] 设f(n)=10n2+20n。则有
    f(n)=O(n2)
   f(n)=(n2)
    f(n)= (n2)

[例2]  设f(n)=aknk+ak-1nk-1+…+a1n+ a0 ,(ak>0)。则有
     f(n)=O(nk)
     f(n)=(nk)
     f(n)= (nk)
四、举例
1.3. 分析复杂度的基本步骤
[例3] 设f(n)= 2n ，g(n)= n! 。则有
     f(n)=O(g(n))
     但是，f(n)(g(n))
     因此，f(n) (g(n))
此时，记作O(f(n)) < O(g(n))。
四、举例
1.3. 分析复杂度的基本步骤
各种复杂度比较示意图如下。
五、复杂度比较示意图
1.3. 分析复杂度的基本步骤
各种复杂度比较示意图如下。
五、复杂度比较示意图
1.4. 复杂度的有关概念
一、算法时间复杂度
对于算法的时间复杂度，通常从分平均、最坏、最好几种情形来衡量，尤其是前两种。
算法的平均复杂性    设Dn是对于所考虑问题来说大小为n的输入的集合，并设i是Dn的一个元素，p(i)是i出现的概率，t(i)是算法在输入i时所执行的基本运算次数。那么，算法的平均复杂性定义为：    A(n)=  i∈Dn p(i)t(i)
算法的最坏复杂性    W(n)= MAX i∈Dnt(i)
算法的最好复杂性    B(n)= MIN i∈Dnt(i)
1.4. 复杂度的有关概念
[例1] 检索问题的顺序查找算法1.1。 以元素的比较作为基本操作。考虑成功检索的情况。
最好情况下的时间复杂度： (1)
最坏情况下的时间复杂度： (n)
在等概率前提下，平均情况下的时间复杂度： (n)
二、举例
算法分析方法
例：顺序搜索算法
template
int seqSearch(Type *a, int n, Type k)
{
for(int i=0;i if (a[i]==k) return i;
return -1;
}
（1）Tmax(n) = max{ T(i) | size(i)=n }=O(n)
（2）Tmin(n) = min{ T(i) | size(i)=n }=O(1)
（3）在平均情况下，假设：
(a) 搜索成功的概率为p ( 0  p  1 )；
(b) 在数组的每个位置i ( 0  i < n )搜索成功的概率相同，均为 p/n。
1.4. 复杂度的有关概念
[例2] 直接插入排序算法1.5。     
以元素的比较作为基本操作。
最好情况下的时间复杂度： (n)
最坏情况下的时间复杂度：
在等概率前提下，平均情况下的时间复杂度：
二、举例
算法分析的基本法则
非递归算法：
（1）for / while 循环
循环体内计算时间*循环次数；
（2）嵌套循环
循环体内计算时间*所有循环次数；
（3）顺序语句
各语句计算时间相加；
（4）if-else语句
if语句计算时间和else语句计算时间的较大者。
template
void insertion_sort(Type *a, int n)
{
Type key; // cost times
for (int i = 1; i < n; i++){ // c1 n
key=a[i]; // c2 n-1
int j=i-1; // c3 n-1
while( j>=0 && a[j]>key ){ // c4 sum of ti
a[j+1]=a[j]; // c5 sum of (ti-1)
j--; // c6 sum og (ti-1)
}
a[j+1]=key; // c7 n-1
}
}
在最好情况下，ti=1, for 1  i 在最坏情况下，ti  i+1, for 1  i 对于输入数据a[i]=n-i,i=0,1,…,n-1，算法insertion_sort 达到其最坏情形。因此，

由此可见，Tmax(n)= (n2)
1.5. 分析和求解复杂度的方法
根据循环来统计基本操作的次数
利用递归关系来表示基本操作的次数
用平摊的办法来统计基本操作的次数(Amortized Analysis)
一、统计算法基本运算的基本方法
1.5. 分析和求解复杂度的方法
[例1] 根据循环来统计基本操作的次数
Input: n= （k为某个正整数）.Output: count（step 4的执行次数）　1.　count←0 　2.　while n≥1 　3. 　for j←1 to n　4. count←count+1 　5. 　end for 6. 　n←n/2  7.　end while  8.　return count
解：基本操作的次数为
1.5. 分析和求解复杂度的方法
[例2] 利用递归关系来求基本操作的次数  
    求Fibonacci数列的第n项。该数列的定义为： 　　     F0= F1=1, Fi= Fi-1 + Fi-2，i  2。 由这一数学定义自然地导出一个递归算法。
int F ( int  n )
{ if(n==0||n==1) return 1;
else if(n>=2) return F(n-1)+F(n-2);
}
解：该算法的计算时间T(n)满足递归方程：
T(n)=T(n-1)+T(n-2)+1, n>1；
初始条件 T(0)=T(1)=0。
1.5. 分析和求解复杂度的方法
[例3]   用平摊的办法来统计基本操作的次数（Amortized Analysis）(1.13)

整型数组A(1：n)初始化为n个正整数的集合,双链表List初始化为仅含一个
元素0

for(j=1;j<=n;j++)
x=A(j);
将 x 插入到表List尾
if x 是偶数 then
while 表List中x的前面元素为奇数
在表List中删除x的前面的那个元素
end while
end if
end for
解：算法的基本操作为元素的插入和删除操作。算法中插入操作的次数为 n 次，而删除操作的次数最多为n-1次，所以，算法的基本操作最少n次，最多2n-1次。
1.5. 分析和求解复杂度的方法
1．典型的求和公式      0 i  n f(i)
二、求解算法复杂度的基本方法
1.5. 分析和求解复杂度的方法
2.       积分近似求和
 如果连续函数f(n)是单调递减的，则有


 如果连续函数f(n)是单调递增的，则有
1.5. 分析和求解复杂度的方法
1.5. 分析和求解复杂度的方法
1.5. 分析和求解复杂度的方法
1.5. 分析和求解复杂度的方法
递归是一种重要的程序设计方法。有些问题的算法运用递归过程来表示不仅自然简洁，而且也易于验证其正确性。递归算法的特点就是：易读，易写，易证。递归和归纳紧密相关。归纳定义的东西往往易写出其递归的算法；而递归的算法往往可用归纳法来证明 。递归算法的时间复杂度分析往往需要借助于求解递归方程或者递归不等式的解得到。
递归方程的类型较多，涉及到的数学知识也较多。这里我们仅简单地介绍分析算法复杂度时常见的几类简单递归方程的求法。
三、递归关系
1.5. 分析和求解复杂度的方法
常用方法：展开法、差分方程法、换元法、数学归纳法等。
三、递归关系
1.5. 分析和求解复杂度的方法
（1） 线性非齐次递归方程

主要解法：差分方程法、数学归纳法等。
1.5. 分析和求解复杂度的方法
1.5. 分析和求解复杂度的方法
1.5. 分析和求解复杂度的方法
1.6.最优算法(optimal algorithm)
如果能够证明求解问题P的任何算法的时间是 (f(n)), 那么称求解问题P的时间为 O(f(n))的任一算法为问题P的最优算法。
一、最优算法
1.6.最优算法(optimal algorithm)
可以证明，任何使用元素的比较给n个元素的数组进行排序的算法的最坏情况运行时间一定是(nlogn)。因此，归并排序、堆排序算法都是最优算法。
二、基于比较的排序问题