03-空间复杂度

未匹配的标注

算法的空间复杂度

定义:空间开销(内存开销,S(n))与问题规模n之间的关系

算法原地工作: 算法所需内存空间为常量

规则:

  • 只需关注存储空间大小与问题规模相关的变量
  • 加法规则、乘法规则、算法好坏判定与时间复杂度一样
  • 递归调用的大多数情况:空间复杂度=递归调用的深度

03-空间复杂度

无变量

03-空间复杂度

变量固定大小

03-空间复杂度

数组

03-空间复杂度

二维数组

03-空间复杂度

递归(内部变量)

  • S(n)= kn
  • 之后不断调用,每一层退出栈

03-空间复杂度

03-空间复杂度

递归(数组)

03-空间复杂度

03-空间复杂度

本文章首发在 LearnKu.com 网站上。

上一篇 下一篇
讨论数量: 0
发起讨论 只看当前版本


暂无话题~