如何评估算法时间开销？
存在的问题
- 和机器性能有关
- 和编程语言有关
- 和编译程序产生的机器指令质量有关
- 有些算法不能事后统计运行时间的——>如导弹控制算法
算法的时间复杂度——>T=T(n)
事前预估算法时间开销T(n) 与 问题规模n的关系（T表示“time”）
算法的时间复杂度
用算法表示“爱你三千遍”
//算法一——逐步递增型
void loveYou(int n) { //n为问题规模
int i = 1; //爱你的程度
while(i <= n){
i++; //每次+1
printf("I Love You %d\n", i);
}
printf("I Love You More Than %d\n", n);
}
int main(){
loveYou(3000);
}
语句频度：
int i=1;——1次while(i<=n)——3001次i++;和printf("I Love You %d\n", i);——3000次printf("I Love You More Than %d\n", n);——1次
T(3000)=1+3001+2*3000+1
时间开销与问题规模n的关系：
T(n)=3n+3
问题：是否可以忽略表达式的某些部分？
如：
T
1
(
n
)
=
3
n
+
3
T_1(n)=3n+3
T1(n)=3n+3
T
2
(
n
)
=
n
2
+
3
n
+
1000
T_2(n)=n^2+3n+1000
T2(n)=n2+3n+1000
T
3
(
n
)
=
n
3
+
n
2
+
99999999
T_3(n)=n^3+n^2+99999999
T3(n)=n3+n2+99999999
不难发现，当问题规模n足够大的时候，后面低阶的部分和常数都可以被忽略掉
所以时间复杂度只需要考虑最高阶的部分
所以以上算法都可以简化为：
T
1
(
n
)
=
n
T_1(n)=n
T1(n)=n
T
2
(
n
)
=
n
2
T_2(n)=n^2
T2(n)=n2
T
3
(
n
)
=
n
3
T3(n)=n^3
T3(n)=n3
1）加法规则
T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n)+g(n)))
多项相加，只保留最高阶的项，且系数变为1
2）乘法规则
T(n)=T1(n)
×
\times
×T2(n)=O(f(n))
×
\times
×O(g(n))=O(f(n)
×
\times
×g(n))
多项相乘，都保留
如:
T
3
(
n
)
=
n
3
+
n
2
log
2
n
=
O
(
n
3
)
+
O
(
n
2
log
2
n
)
=
O
(
n
3
)
T_3(n)=n^3+n^2\log_2n =O(n^3)+O(n^2\log_2n) =O(n^3)
T3(n)=n3+n2log2n=O(n3)+O(n2log2n)=O(n3)
常见数量级的时间复杂度排序
O ( 1 ) < O ( l o g 2 n ) < O ( n ) < O ( n l o g 2 n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) < O ( n ! ) < O ( n n ) O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n) O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
//算法二——嵌套循环型
void loveYou(int n){
int i=1;
while(i<=n){
i++;
printf("I Love You %d\n", i);
for (int j=1; j<=n; j++){
printf("I am Iron Man\n");
}
}
printf("I Love You More Than %d\n", n);
}
外层循环执行
n
n
n次，内层循环执行
n
2
n^2
n2次
时间开销与问题规模
n
n
n的关系：
T
(
n
)
=
O
(
n
)
+
O
(
n
2
)
=
O
(
n
2
)
T(n)=O(n)+O(n^2)=O(n^2)
T(n)=O(n)+O(n2)=O(n2)
结论
- 顺序执行的代码只会影响常数项，可以忽略
- 只需要挑循环中的一个基本操作分析它的执行次数与 n n n的关系即可
- 如果有多层嵌套循环，只需关注最深层循环循环了几次
小练习
练习一
//算法三——指数递增型
void loveYou(int n){
int i=1;
while(i<=n){
i=i*2;
printf("I Love You %d\n", i);
}
printf("I Love You More Than %d\n", n);
}
时间复杂度：
设最深层循环的语句频度（总共循环的次数）为
x
x
x，则
由循环条件可知，循环结束时刚好满足
2
x
>
n
2^x>n
2x>n
x
=
l
o
g
2
n
+
1
x=log_2n+1
x=log2n+1
T
(
n
)
=
O
(
x
)
=
O
(
l
o
g
2
n
)
T(n)=O(x)=O(log_2n)
T(n)=O(x)=O(log2n)
练习二
//算法四——搜索数字型
void loveYou(int flag[], int n){
printf("I Am Iron Man\n");
for(int i=0; i<n; i++){ //从第一个元素开始查找
if(flag[i]==n){ //找到元素n
printf("I Love You %d\n", n);
break; //找到后立即跳出循环
}
}
}
//flag数组中乱序存放了1～n这些数
int flag[n]={1...n};
loveYou(flag, n)
时间复杂度：
- 最好情况：元素n在第一个位置——最好时间复杂度T(n)=O(1)
- 最坏情况：元素n在最后一个位置——最坏时间复杂度T(n)=O(n)
- 平均情况：假设元素n在任意一个位置的概率相同为
1/n——平均时间复杂度T(n)=O(n)
循环次数：
x = ( 1 + 2 + 3 + . . . + n ) 1 n = ( n ( 1 + n ) 2 ) 1 n = 1 + n 2 x=(1+2+3+...+n)\frac{1}{n}=(\frac{n(1+n)}{2})\frac{1}{n}=\frac{1+n}{2} x=(1+2+3+...+n)n1=(2n(1+n))n1=21+n
知识回顾与重要考点
时间复杂度
如何计算
- 找到一个基本操作（最深层循环）
- 分析该基本操作的执行次数
x与问题规模n的关系x=f(n) x的数量级O(x)就是算法时间复杂度T(n)
常用技巧
- 加法规则
- 乘法规则
- “常对幂指阶”
三种复杂度
- 最坏时间复杂度
- 平均时间复杂度
- 最好时间复杂度