第 2章 算法分析算法分析的概念算法效率的度量检验一个算法分析
Big-Oh分析法的限制评价算法好坏的标准执行算法所耗费的时间，即效率问题。
执行算法所耗费的存储空间，主要考虑辅助的存储空间。
算法应易于理解,具有可读性，易于编码，易于调试等。
健壮性，即当输入一些非法数据时，算法也应做出适当的反映或进行处理。
算法分析的概念算法所花费的运行时间取决于它所处理的数据输入量。
算法的运行时间是数据输入量的一个函数。
而确切的函数值依赖于许多因素。
对于一个给定计算机上的给定程序，可以在图中描绘出运行时间的函数。
图中给出了四个程序的运行时间图，这些曲线代表了在算法分析中遇到的四个函数：线性函数,O（ NlogN）、二次方函数、立方函数，输入规模 N从 1至 100，运行时间为 0至 10毫秒。
算法分析中的时间函数图解图 2-1 小规模输入时的运行时间 图 2-2 中规模输入时的运行时间这些曲线最显著的特征就是当数据输入量较大时，平方算法和立方算法无法与其他算法竞争。
下表所示的是以增长率的增长次序来排列这些算法运行时间的函数。
函数 名称 函数 名称
c 常数 NlogN NlogN
logN 对数 N2 平方
log 2N 平方对数 N3 立方
N 线性 2? 指数算法效率的度量算法效率 —— 用依据该算法编制的程序在计算机上执行所 消耗的时间 来度量。
通常有两种衡量算法效率的方法,
1,事后统计 —— 利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分。
缺点,?必须先运行依据算法编制的程序。
所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣。
算法效率的度量
2,事前分析估计 —— 一个高级语言程序在计算机上运行所消耗的时间取决于：
依据的算法选用何种策略
问题的规模
程序语言
编译程序产生机器代码质量
机器执行指令速度算法效率的度量同一个算法用不同的语言、不同的编译程序、
在不同的计算机上运行，效率均不同,—— 所以使用 绝对时间单位 衡量算法效率 不合适。
一个特定算法的,运行工作量,的大小，只依赖于问题的规模（通常用整数量 n表示），或者说，
它是问题规模的函数。
计算累加和程序程序步数计算工作表格程 序 语 句一次执行所需程序步数执行频度程序步数
{ 0 1 0
float s = 0.0 ; 1 1 1
for ( int i= 0 ; i< n ; i+ + ) 1 n+1 n+1
s += a[i] ; 1 n n
return s ; 1 1 1
} 0 1 0
总程序步数 2n+3
算法效率的度量一般情况下，算法中基本操作重复执行的次数是问题规模 n的某个函数，算法的时间量度记作
T(n)=O(f(n))
称作算法的 渐近时间复杂度,简称 时间复杂度 。
表示随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同。
算法效率的度量例１,N× N矩阵相乘
for(I=1,I<=n;++I)
for(j=1;j<=n;++j)
{c[I][j]=0;
for(k=1;k<=n;++k)
c[I][j]+=a[I][k]*b[k][j];
}
由于是一个三重循环，每个循环从 1到 n，则总次数为,
n× n× n=n3
时间复杂度为 T(n)=O(n3)
算法效率的度量频度,是指该语句重复执行的次数。
例２ {++x;s=0;}
将 x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ (1)。
如果将 s=0也看成是基本操作，则语句频度为２，
其时间复杂度仍为Ｏ (1)，即 常量阶 。
算法效率的度量例３,for(I=1;I<=n;++I)
{++x;s+=x;}
语句频度为,2n，其时间复杂度为,O(n)
即时间复杂度为 线性阶 。
例４,for(I=1;I<=n;++I)
for(j=1;j<=n;++j)
{++x;s+=x;}
语句频度为,2n2 其时间复杂度为,O(n2)
即时间复杂度为 平方阶 。
算法效率的度量由于算法的时间复杂度考虑的只是对于问题规模 n的增长率，则在难以精确计算基本操作执行次数（或语句频度）的情况下，只需要求出它关于 n
的增长率或阶即可 。
算法效率的度量定理,若 A(n)=am nm +am-1 nm-1 +… +a1n+a0是一个 m次多项式，则
A(n)的 T(n)=O(nm) 证略。
例５ for(i=2;i<=n;++I)
for(j=2;j<=i-1;++j)
{++x;a[i,j]=x;}
语句频度为：
0+1+2+3+… +n-2=(0+n-2) × (n-1)/2
=(n-1)(n-2)/2 = n2-3n+2
∴ 时间复杂度为 O(n2)，即此算法的时间复杂度为平方阶。
算法效率的度量双重循环的渐近时间复杂度不一定是 O(n2)。
例 6,sum1=0;
for(k=1;k<=n;k*=2)
for(j=1;j<=n;j++)
sum1++;
其中外循环每循环一次,k乘以 2，直到 k>n。
k依次取值,20,21,22,2i＞ n。
内循环执行 n次。
时间代价为：
T(n)=O（ nlog2 n）
算法效率的度量以下六种计算算法时间的多项式是最常用的。其关系为：
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)
指数时间的关系为,O(2n)<O(n!)<O(nn)
当 n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。
算法效率的度量有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同 。例如：
Void bubble-sort(int a[],int n)
for(I=n-1,change=TURE;I>=1 && change;--I)
{ change=false;
for(j=0;j<I;++j)
if (a[j]>a[j+1]) {
a[j] ←→a[j+1];
change=TURE} }
算法效率的度量最好情况,0次最坏情况,1+2+3+… +n-1
=n(n-1)/2
平均时间复杂度为,O(n2)
大 O表示法的一些算术规则
加法规则：适用于并列程序段
T(n,m) = T1 (n) + T2 (m)
= O(max (f (n),g (m)))
乘法规则：适用于嵌套程序段
T (n,m) = T1 (n) * T2 (m)
= O(f (n)*g (m))
课堂练习：算法分析例如：
for (i=1; i<=n; ++i)
for (j=1; j<=n; ++j) {
c[i][j] = 0;
for (k=1; k<=n; ++k)
c[i][j] += a[j][k] * b[k][j];
}
时间复杂度 T(n) = O(n3)
例如：
for (i=2; i<=n; ++i)
for (j=2; j<=i-1; ++j) {
++x;
a[i][j] = x;
}
时间复杂度 T(n) = O(n2)
检验一个算法分析判断算法是否正确：编写这个程序，看通过算法分析预测到的运行时间与实际观测到的运行时间是否一致。
Big-Oh分析法的限制表现一,算法分析忽略了常数，不区分内存存取（非常快）和磁盘存取（花费的时间多得多），总是假设内存无穷大。
表现二,常数项和低次项被考虑到，分析则估计过高。
Big-Oh分析法的限制评价算法好坏的标准执行算法所耗费的时间，即效率问题。
执行算法所耗费的存储空间，主要考虑辅助的存储空间。
算法应易于理解,具有可读性，易于编码，易于调试等。
健壮性，即当输入一些非法数据时，算法也应做出适当的反映或进行处理。
算法分析的概念算法所花费的运行时间取决于它所处理的数据输入量。
算法的运行时间是数据输入量的一个函数。
而确切的函数值依赖于许多因素。
对于一个给定计算机上的给定程序，可以在图中描绘出运行时间的函数。
图中给出了四个程序的运行时间图，这些曲线代表了在算法分析中遇到的四个函数：线性函数,O（ NlogN）、二次方函数、立方函数，输入规模 N从 1至 100，运行时间为 0至 10毫秒。
算法分析中的时间函数图解图 2-1 小规模输入时的运行时间 图 2-2 中规模输入时的运行时间这些曲线最显著的特征就是当数据输入量较大时，平方算法和立方算法无法与其他算法竞争。
下表所示的是以增长率的增长次序来排列这些算法运行时间的函数。
函数 名称 函数 名称
c 常数 NlogN NlogN
logN 对数 N2 平方
log 2N 平方对数 N3 立方
N 线性 2? 指数算法效率的度量算法效率 —— 用依据该算法编制的程序在计算机上执行所 消耗的时间 来度量。
通常有两种衡量算法效率的方法,
1,事后统计 —— 利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分。
缺点,?必须先运行依据算法编制的程序。
所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣。
算法效率的度量
2,事前分析估计 —— 一个高级语言程序在计算机上运行所消耗的时间取决于：
依据的算法选用何种策略
问题的规模
程序语言
编译程序产生机器代码质量
机器执行指令速度算法效率的度量同一个算法用不同的语言、不同的编译程序、
在不同的计算机上运行，效率均不同,—— 所以使用 绝对时间单位 衡量算法效率 不合适。
一个特定算法的,运行工作量,的大小，只依赖于问题的规模（通常用整数量 n表示），或者说，
它是问题规模的函数。
计算累加和程序程序步数计算工作表格程 序 语 句一次执行所需程序步数执行频度程序步数
{ 0 1 0
float s = 0.0 ; 1 1 1
for ( int i= 0 ; i< n ; i+ + ) 1 n+1 n+1
s += a[i] ; 1 n n
return s ; 1 1 1
} 0 1 0
总程序步数 2n+3
算法效率的度量一般情况下，算法中基本操作重复执行的次数是问题规模 n的某个函数，算法的时间量度记作
T(n)=O(f(n))
称作算法的 渐近时间复杂度,简称 时间复杂度 。
表示随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同。
算法效率的度量例１,N× N矩阵相乘
for(I=1,I<=n;++I)
for(j=1;j<=n;++j)
{c[I][j]=0;
for(k=1;k<=n;++k)
c[I][j]+=a[I][k]*b[k][j];
}
由于是一个三重循环，每个循环从 1到 n，则总次数为,
n× n× n=n3
时间复杂度为 T(n)=O(n3)
算法效率的度量频度,是指该语句重复执行的次数。
例２ {++x;s=0;}
将 x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ (1)。
如果将 s=0也看成是基本操作，则语句频度为２，
其时间复杂度仍为Ｏ (1)，即 常量阶 。
算法效率的度量例３,for(I=1;I<=n;++I)
{++x;s+=x;}
语句频度为,2n，其时间复杂度为,O(n)
即时间复杂度为 线性阶 。
例４,for(I=1;I<=n;++I)
for(j=1;j<=n;++j)
{++x;s+=x;}
语句频度为,2n2 其时间复杂度为,O(n2)
即时间复杂度为 平方阶 。
算法效率的度量由于算法的时间复杂度考虑的只是对于问题规模 n的增长率，则在难以精确计算基本操作执行次数（或语句频度）的情况下，只需要求出它关于 n
的增长率或阶即可 。
算法效率的度量定理,若 A(n)=am nm +am-1 nm-1 +… +a1n+a0是一个 m次多项式，则
A(n)的 T(n)=O(nm) 证略。
例５ for(i=2;i<=n;++I)
for(j=2;j<=i-1;++j)
{++x;a[i,j]=x;}
语句频度为：
0+1+2+3+… +n-2=(0+n-2) × (n-1)/2
=(n-1)(n-2)/2 = n2-3n+2
∴ 时间复杂度为 O(n2)，即此算法的时间复杂度为平方阶。
算法效率的度量双重循环的渐近时间复杂度不一定是 O(n2)。
例 6,sum1=0;
for(k=1;k<=n;k*=2)
for(j=1;j<=n;j++)
sum1++;
其中外循环每循环一次,k乘以 2，直到 k>n。
k依次取值,20,21,22,2i＞ n。
内循环执行 n次。
时间代价为：
T(n)=O（ nlog2 n）
算法效率的度量以下六种计算算法时间的多项式是最常用的。其关系为：
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)
指数时间的关系为,O(2n)<O(n!)<O(nn)
当 n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。
算法效率的度量有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同 。例如：
Void bubble-sort(int a[],int n)
for(I=n-1,change=TURE;I>=1 && change;--I)
{ change=false;
for(j=0;j<I;++j)
if (a[j]>a[j+1]) {
a[j] ←→a[j+1];
change=TURE} }
算法效率的度量最好情况,0次最坏情况,1+2+3+… +n-1
=n(n-1)/2
平均时间复杂度为,O(n2)
大 O表示法的一些算术规则
加法规则：适用于并列程序段
T(n,m) = T1 (n) + T2 (m)
= O(max (f (n),g (m)))
乘法规则：适用于嵌套程序段
T (n,m) = T1 (n) * T2 (m)
= O(f (n)*g (m))
课堂练习：算法分析例如：
for (i=1; i<=n; ++i)
for (j=1; j<=n; ++j) {
c[i][j] = 0;
for (k=1; k<=n; ++k)
c[i][j] += a[j][k] * b[k][j];
}
时间复杂度 T(n) = O(n3)
例如：
for (i=2; i<=n; ++i)
for (j=2; j<=i-1; ++j) {
++x;
a[i][j] = x;
}
时间复杂度 T(n) = O(n2)
检验一个算法分析判断算法是否正确：编写这个程序，看通过算法分析预测到的运行时间与实际观测到的运行时间是否一致。
Big-Oh分析法的限制表现一,算法分析忽略了常数，不区分内存存取（非常快）和磁盘存取（花费的时间多得多），总是假设内存无穷大。
表现二,常数项和低次项被考虑到，分析则估计过高。
