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

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

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

共 10 页PDF · 646.0KB
下载

文档在线预览

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

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

下载

文档文本内容

本节内容
算法
效率的度量
王道考研/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