事前分析估算的方法
亲蜜爱人-金融危机产生的原因
事前分析估算的方法
假设给定的是一台通用计算机，满足：
执行一条基本语句或一个基本运算需花一个单位时间
基本语句指：赋值语句、输入语句、输出语句
基本运算指：算术运算、一次比较（字符比较、数值比较）
做法：从算法中选取一种对于
所研究的问题（或算法类型）来说是基本操作的原操作，以
该基本操作重复执行的次数作为算法的时间量
度。
例8-1 两个N×N矩阵A和B相乘的算法。
for (i=0;i
for
(k=0;k
}
时间复杂度：基本操作重复执行的次数是问题规模n的某个函数，记作T(n)=O(f(n))
“O” 标记的形式定义：
若f(n)是正整数n的一个函数，则xn＝O(f(n))表示存在一个
正的常数M，使得当nn0时都
满足|xn|M|f(n)|；(换句话就是说，这当整型自变量n
趋向于无穷大时，两者的比值是一个
不等于0的常数。)
例8-2
N×N矩阵相乘的算法的时间复杂度：
基本操作执行的次数：n×n×n=n
3
∴T(n)=O(n
3
)
语句的频度：是指该语句重复执行的次数。与该语句包含的基本操作执行的次数相同。
例8
分析语句{++x; s=0;}的频度。
解：将“++x”看成是基本操作，则语句频度为１，即时
间复杂度为
Ｏ
(1)；如果将“s=0”也看
成是基本操作，则语句频度为２，其时间
复杂度仍为
Ｏ
(1)，即常量阶。
例9 分析语句for (i=1; i<=n;
++i)
{++x; s+=x;}
解：语句频度为：2n，其时间复杂度为：T(n)=O(n)。即时间复杂度为线性阶。
例10 分析语句for (i=1; i<=n; ++i)
for (j=1;
j<=n; ++j)
{++x; s+=x;}
解：语句频度为：2n
2
，其时间复杂度为：O(n
2
)。即时间复杂度为平方阶。
定理：若A(n)=a
m
n
m
+a
m-1
n
m-1
+…+a
1
n+a
0
是一个m次多项式，则A(n)=O(n
m
)。(证明
略)
例11 for (i=2; i<=n; ++i)
for (j=2; j<=i-1; ++j)
{++x; a[i,j]=x;}
解：语句的频度为：
1+2+3+…+n-2=(1+n-2) ×(n-2)2
=(n-1)(n-2)2
=(n2-3n+2)2
∴时间复杂度为T(n)=O(n2)
即此算法的时间复杂度为平方阶。
练习：x=n; y=0;
while (x >= (y + 1)(y
+ 1)){
y++;}
以下六种计算算法时间复杂度的多项式是最常用的。其关系为：
O(1)
O(2n)
分析并确定：算法的哪些参数决定算法的“输入规模”？
明确：被分析算法的“基本操作”是什么？
算法分析的目标：考察算法的“基本操作”数，随“问题规模”而变化的规律。
算法时间复杂度的渐进表示。
算法的最坏情况下的复杂度
设：I是问题规模为n的所有
输入的集合，i∈I是问题的一个输入实例。ti(n)是输入i下，
算法A的“关键操作”数。则，算
法A的最坏情况复杂度：
WA(n) =
平均复杂度
设：I是问题规模为n的所有输入的集合， i∈I是问题的一个输入实例。ti(n)是输入i下，<
br>算法A的“关键操作”数。Pi(n)是输入i出现在I中的概率。则，算法A的平均时间复杂度：
AVA(n) = ∑(Pi(n)ti(n))
i∈I
例12 冒泡排序算法。
Void bubble-sort(int a[], int n)
for(i=n-1;change=TURE;i>1 && change;--i)
{change=false;
for(j=0;j
a[j]←→a[j+1];
change=TURE}
}
分析：
问题的输入规模：n；
基本操作：“交换序列中相邻两个整数”；
实例：5 1 9 7 3 2
3 1 2 5 9 7
“基本操作”数随n变化的规律：
a中序列自小至大有序时，“基本操作”数为0；
a中序列自大至小有序时，“基本操作”数为
= =(1+2+3+...+(n-1))=n(n-1)2
算法的时间复杂度：
最好情况下的时间复杂度：0
最坏情况下的时间复杂度：W(n) =n(n-1)2
平均情况下的时间复杂度：
AV(n) = 1n![0+1+2+...+n(n-1)2]=O(n2)
总结：
确定算法问题规模；
找出基本操作；
分析基本操作是否只依赖于问题规模？
是，就直接建立基本操作执行次数的求和表达式，并求解、用渐进符号表示；
否则，分别对该算法的最好、最坏和平均情况的时间复杂度进行分析。
算法的存储空间代价
一个算法的空间效率是指在算法的执行过程中，所占据的辅助空间数量。
空间复杂度：算法所需存储空间的度量，记作
S(n)=O(f(n))
其中，n为问题的规模。