数据结构前置知识

Breeze Shane大约 2 分钟

基本概念

算法效率的度量是通过时间复杂度与空间复杂度两方面来描述的，使用的数学概念是函数渐近的界，详细信息去往算法基础。

一个语句的频度是指该语句在算法中被重复执行的次数，而算法中所有语句的频度之和记为 $T(n)$ ，而算法中基本运算的频度与 $T(n)$ 同数量级，故通常采用算法中基本运算的频度 $f(n)$ 来分析算法的时间复杂度，故而算法时间复杂度记为 $T(n) = O(f(n))$ 。

加法规则：

T(n) = T_1(n) + T_2(n) = O(f(n)) + O(g(n)) = O(\max\{f(n),g(n)\})

乘法规则：

T(n) = T_1(n) \times T_2(n) = O(f(n)) \times O(g(n)) = O(f(n)\times g(n))

常见的复杂度阶级排序为：

O(1) < O(\log_2n) < O(n) < O(n\log_2n) < O(n^2) < O(n^3) < O(2^n) <O(n!) < O(n^n)

算法的空间复杂度 $S(n)$ 定义为该算法所耗费的存储空间，它是问题规模 $n$ 的函数，即 $S(n)=O(g(n))$ 。

一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。

若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间。

算法原地工作指：算法所需的辅助空间为常量，即 $O(1)$ 。