夜雨聆风学习资料网 资料列表 开通 VIP 用登录 / 注册 ⌄
PDF

1.2_2_算法的时间复杂度_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第一章绪论

查看资料信息、公开预览和下载状态。

共 17 页PDF · 1.2MB
下载

文档在线预览

公开展示前 9 页
100%
1
《1.2_2_算法的时间复杂度_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第一章绪论》第1页预览
2
《1.2_2_算法的时间复杂度_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第一章绪论》第2页预览
3
《1.2_2_算法的时间复杂度_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第一章绪论》第3页预览
4
《1.2_2_算法的时间复杂度_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第一章绪论》第4页预览
5
《1.2_2_算法的时间复杂度_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第一章绪论》第5页预览
6
《1.2_2_算法的时间复杂度_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第一章绪论》第6页预览
7
《1.2_2_算法的时间复杂度_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第一章绪论》第7页预览
8
《1.2_2_算法的时间复杂度_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第一章绪论》第8页预览
9
《1.2_2_算法的时间复杂度_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第一章绪论》第9页预览

本文档共 17 页 剩余 8 页未展示,请下载后查阅

下载

文档文本内容

本节内容
算法
效率的度量
王道考研/CSKAOYAN.COM知识总览
王道考研/CSKAOYAN.COM如何评估算法时间开销?
让算法先运行,事后统计运行时间?
存在什么问题?
• 和机器性能有关,如:超级计算机 v.s. 单片机 能否排除与算法本
身无关的外界因素
• 和编程语言有关,越高级的语言执行效率越低
• 和编译程序产生的机器指令质量有关
能否事先估计?
• 有些算法是不能事后再统计的,如:导弹控制算法
算法时间复杂度
事前预估算法时间开销T(n)与问题规模 n 的关系(T 表示 “time”)
王道考研/CSKAOYAN.COM算法的时间复杂度
用算法表白 “爱你 遍”
—— n
王道考研/CSKAOYAN.COM算法的时间复杂度
①
②
③
④
⑤
语句频度:
① ——1次
② ——3001次
问题1:是否可以忽略表达式
③④ ——3000次
某些部分?
⑤ ——1次
T(3000) = 1 + 3001 + 2*3000 + 1 问题2:如果有好几千行代码,
时间开销与问题规模 n 的关系: 按这种方法需要一行一行数?
T(n)=3n+3
王道考研/CSKAOYAN.COM算法的时间复杂度 全称:渐进时间复杂度
时间开销与问题规模 n 的关系:
问题1:是否可以忽略表达式
某些部分?
T (n)=3n+3
1
当问题规模 n 足够大时…
T (n)=n2+3n+1000
2
T (n) = O(n)
大O表示“同阶”,同等
1
数量级。即:当 nà∞时, T (n) = O(n2) 简化
2 T (n)=n3 + n2 +9999999
二者之比为常数 T (n) = O(n3) 3
3
若 n=3000,则
3n = 9000 V.S. T (n)= 9003
1
结论1:可以只考虑阶数高的部分
n2 = 9,000,000 V.S. T (n)= 9,010,000
2
n3 = 27,000,000,000 V.S. T (n)= 27,018,999,999
3
结论2:问题规模足够大时,
当 n=3000 时,9999n = 29,997,000 远小于 n3 = 27,018,999,999
常数项系数也可以忽略
当 n=1000000时,9999n = 9,999,000,000 远小于 n2= 1,000,000,000,000
王道考研/CSKAOYAN.COM算法的时间复杂度
时间开销与问题规模 n 的关系:
问题1:是否可以忽略表达式
某些部分?
T (n)=3n+3
1
当问题规模 n 足够大时…
T (n)=n2+3n+1000
2
T (n) = O(n)
1
T (n) = O(n2) 简化
2 T (n)=n3 + n2 +9999999
T (n) = O(n3) 3
3
a)加法规则
T(n) = T (n) + T (n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
1 2
多项相加,只保留最高阶的项,且系数变为1
b)乘法规则
T(n) = T (n)×T (n) = O(f(n))×O(g(n)) = O(f(n)×g(n))
多项相乘,都保留
1 2
Eg:T (n)= n3 + n2 log n
3 2
= O(n3) + O(n2 log n)
2
= ???
王道考研/CSKAOYAN.COM算法的时间复杂度
O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3)< O(2n)< O(n!) < O(nn)
2 2
问题:两个算法的时间复杂度分别如下,哪个的阶数更高(时间复杂度更高)?
T (n) = O(n)
1
T (n) = O(log n)
2 2
Eg:T (n)= n3 + n2 log n
3 2
= O(n3) + O(n2 log n)
2
= O(n2n) + O(n2 log n)
2
log 2 n 洛必达 1 当 nà∞ 时,n 比 log n
lim lim = 0 2
!→# n !→# n𝑙𝑛2 变大的速度快很多
n2 洛必达 2n 洛必达 2
当 nà∞ 时, 2n 比 n2
lim lim lim = 0
!→# 2n !→# 2n𝑙𝑛2 !→# 2n𝑙𝑛22 变大的速度快很多
王道考研/CSKAOYAN.COM算法的时间复杂度
y = 2n
y = n!
只保留更高阶的项
y = n2
a)加法规则
T(n) = T (n) + T (n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
1 2
b)乘法规则
T(n) = T (n)×T (n) = O(f(n))×O(g(n)) = O(f(n)×g(n))
1 2
y=n
y=log n
2
常对幂指阶
y = 1
(cid:14224)(cid:13710)(cid:20723)(cid:14756)
王道考研/CSKAOYAN.COM算法的时间复杂度
①
②
③
④
⑤
语句频度:
① ——1次
问题1:是否可以忽略表达式
② ——3001次
某些部分?
③④ ——3000次
⑤ ——1次
只考虑阶数,用大O记法表示
T(3000) = 1 + 3001 + 2*3000 + 1
时间开销与问题规模 n 的关系: 问题2:如果有好几千行代码,
T(n) = 3n+3 = O(n) 按这种方法需要一行一行数?
王道考研/CSKAOYAN.COM算法的时间复杂度
①
此处插入1000行顺序执行的代码
②
③
④
结论1:顺序执行的代码只会
影响常数项,可以忽略
⑤
结论2:只需挑循环中的一个
语句频度: 基本操作分析它的执行次数
① ——1次 与 n 的关系即可
② ——3001次
③④ ——3000次
⑤ ——1次
T(3000) = 1 + 3001 + 2*3000 + 1 T(3000) = 1000 + 1 + 3001 + 2*3000 + 1
时间开销与问题规模 n 的关系: 时间开销与问题规模 n 的关系:
T(n) = 3n+3 = O(n) T(n) = 3n+1003 = O(n)
王道考研/CSKAOYAN.COM算法的时间复杂度
外层循环执行n次
嵌套两层循环
内层循环共执行n2次
结论1:顺序执行的代码只会
影响常数项,可以忽略
结论2:只需挑循环中的一个
基本操作分析它的执行次数
时间开销与问题规模 n 的关系: 与 n 的关系即可
T(n) = O(n) + O(n2) = O(n2)
结论3:如果有多层嵌套循环,
只需关注最深层循环循环了几次
王道考研/CSKAOYAN.COM算法的时间复杂度
①
②
③
④
⑤
语句频度:
问题1:是否可以忽略表达式
① ——1次
某些部分?
② ——3001次
③④ ——3000次 只考虑阶数,用大O记法表示
⑤ ——1次
问题2:如果有好几千行代码,
T(3000) = 1 + 3001 + 2*3000 + 1 按这种方法需要一行一行数?
时间开销与问题规模 n 的关系:
T(n) = 3n+3 = O(n) 只需考虑最深层循环的循环
次数与 n 的关系
王道考研/CSKAOYAN.COM小练习
1
计算上述算法的时间复杂度 T(n):
设最深层循环的语句频度(总共循环的次数)为 x,则
由循环条件可知,循环结束时刚好满足 2x> n
x = log n + 1
2
T(n) = O(x) = O(log n)
2
王道考研/CSKAOYAN.COM小练习
2
很多算法执行时间与
输入的数据有关
计算上述算法的时间复杂度 T(n)
最好情况:元素n在第一个位置 ——最好时间复杂度 T(n)=O(1)
最坏情况:元素n在最后一个位置 ——最坏时间复杂度 T(n)=O(n)
$
平均情况:假设元素n在任意一个位置的概率相同为 ——平均时间复杂度 T(n)=O(n)
!
$%!
循环次数 x = (1+2+3+…+n) ! = ( "(!$") ) ! = T(n)=O(x)=O(n)
" & " &
王道考研/CSKAOYAN.COM算法的时间复杂度
最坏时间复杂度:最坏情况下算法的时间复杂度
平均时间复杂度:所有输入示例等概率出现的情况下,算法的期望运行时间
最好时间复杂度:最好情况下算法的时间复杂度
王道考研/CSKAOYAN.COM知识回顾与重要考点
小故事:算法的性能问题只有在 n 很大时才会暴露出来。
王道考研/CSKAOYAN.COM