做网站咨询seo人工智能
计算机考研408-数据结构笔记本之——第一章 绪论
1.2 算法和算法评价
1.2.2 算法效率的度量
算法效率的度量是通过时间复杂度和空间复杂度来描述的。
1.空间复杂度
算法的空间复杂度S(n)定义为该算法所需的存储空间，它是问题规模n的函数，记为
S(n) = O(g(n))
2.计算方法
与时间复杂度的计算方法类似，但在概念上有所不同。
（1）举例计算1 (常量计为1）
假设一个int型变量占用4B内存。
①int n —— 4B ②int i = 1 —— 4B
S(n) = 4 + 4 = 8 = 常量 = O(1) (常量计为1）
算法原地工作：如上图代码所示，计算出来的空间复杂度是一个常量，即O(1)，这就叫算法原地工作。
（2）举例计算2（只保留最高项且最高项系数视为1）
假设一个int型变量占用4B内存。
①int n —— 4B ②int flag[n] —— 4nB ③int i —— 4B
S(n) = 4 + 4n + 4 = 4n + 8 = O(n) （只保留最高项且最高项系数视为1）
（3）举例计算3（加法规则和乘法规则）
（4）举例计算4（递归程序）
