【数据结构】算法的时间复杂度与空间复杂度

计算机考研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（递归程序）