空间复杂度

  1. 1. 概述
  2. 2. 详细

空间复杂度

1. 概述

评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。
一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度,可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。

2. 详细

算法得存储量包括:

  1. 程序本身所占空间
  2. 输入数据所占空间
  3. 辅助变量所占空间

输入数据所占空间只取决于问题本身,和算法无关,则只需分析除输入和程序之外得辅助变量所占额外空间。
空间复杂度是对一个算法在运行过程中临时占用得存储空间大小的量度,一般也作为问题规模n得函数,以数量级形式给出,记作:
$$S(n) = O(g(n))$$


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 wind.kaisa@gmail.com

文章标题:空间复杂度

本文作者:kaisawind

发布时间:2020-06-11, 02:06:12

最后更新:2020-11-18, 15:55:44

原始链接:https://kaisawind.gitee.io/2020/06/10/2020-06-11-space-complexity/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏