数据结构复习笔记 - 分析、统计算法的执行效率和资源消耗 下

大 O 复杂度表示法

所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

T(n) = Of(n)

我来具体解释一下这个公式。其中，T(n) 我们已经讲过了，它表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

时间复杂度分析

1. 只关注循环执行次数最多的一段代码
   • 我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
   • 总的时间复杂度就等于量级最大的那段代码的时间复杂度
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
   • T1(n) = O(n)，T2(n) = O(n2)，则 T1(n) * T2(n) = O(n3) 嵌套循环

几种常见时间复杂度实例分析

1. 多项式量级
2. 非多项式量级。非多项式量级只有两个：O(2n) 和 O(n!)。

空间复杂度分析

渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n2)