文档文本内容
本节内容
算法
效率的度量
王道考研/CSKAOYAN.COM知识总览
时间开销与问题规
模 n 之间的关系
空间开销(内存开销)与
问题规模 n 之间的关系
王道考研/CSKAOYAN.COM程序运行时的内存需求
内存
装入 程序
大小固定,与
代码
问题规模无关
数据
局部变量 i,
参数 n …
无论问题规模怎么变,算法运行所需的内存空间
都是固定的常量,算法空间复杂度为
S(n) = O(1)
注:S 表示 “Space”
算法原地工作——算法所需内存空间为常量
王道考研/CSKAOYAN.COM空间复杂度
内存
装入 程序
大小固定,与
代码
问题规模无关
数据
局部变量 i,
参数 n …
数组flag[n]
假设一个 int 变量占 4B…
则所需内存空间 = 4 + 4n + 4 = 4n + 8
只需关注存储空间大小
S(n) = O(n) 与问题规模相关的变量
王道考研/CSKAOYAN.COM空间复杂度
内存
程序
大小固定,与
装入
代码
问题规模无关
数据
局部变量 i,
参数 n …
数组flag[n][n]
S(n) = O(n2)
王道考研/CSKAOYAN.COM空间复杂度
内存
程序
大小固定,与
装入
代码
问题规模无关
数据
局部变量 i,
参数 n …
数组flag[n][n]
数组other[n]
S(n) = O(n2)+O(n)+O(1) = O(n2)
a)加法规则
T(n) = T (n) + T (n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
1 2
O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3)< O(2n)< O(n!) < O(nn)
2 2
王道考研/CSKAOYAN.COM函数递归调用带来的内存开销
内存
程序
大小固定,与
装入
代码
问题规模无关
5
存储函数的参数n,
4 局部变量abc…
3
2
1
调用 调用 调用 调用
loveYou(5) loveYou(4) loveYou(3) loveYou(2) loveYou(1)
返回 返回 返回 返回
王道考研/CSKAOYAN.COM函数递归调用带来的内存开销
内存
程序
大小固定,与
装入
代码
问题规模无关
5
存储函数的参数n,
4 局部变量abc…
3
2
1
S(n) = O(n)
空间复杂度 = 递归调用的深度
调用 调用 调用 调用
loveYou(5) loveYou(4) loveYou(3) loveYou(2) loveYou(1)
返回 返回 返回 返回
王道考研/CSKAOYAN.COM函数递归调用带来的内存开销
内存
程序
大小固定,与
装入
代码
问题规模无关
5
存储参数 n,flag[5]…
4
3
2
1
S(n) = O(n2)
王道考研/CSKAOYAN.COM
……
存储参数 n,flag[4]…
存储参数 n,flag[1]…
! !
1+2+3+…+n = [n(1+n)]/2 = n2 + n
" "知识回顾与重要考点
王道考研/CSKAOYAN.COM