《数据结构与算法之美--复杂度分析》
keyword:
概念，大O表示法，常见的时间复杂度，最好、最坏、平均、均摊时间复杂度
概念:
- 时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关
系 - 空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的
存储空间与数据规模之间的增长关系
大O表示法：
-
T（n）=O（f(n)）
备注：T(n)表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。公式中的
O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。-
例子：
def cal(n): sum = 0#运行一次 for range(n): #运行N次 sum = sum + i;#运行N次 return sum; }T(n)=O(2n+1)
备注：时间复杂度只看最高项，所以可简写为O(n)！
常见的时间复杂度：
- O(1)、O(logn)、O(nlogn)、O( 2n
指数表示)，O(n!) - 时间复杂度为O(2n
指数表示) 和 O(n!)的算法称为NP（Non-Deterministic Polynomial，非确定多项
式）问题，因为其随着规模扩大，时间复杂度爆炸式增长，效率十分低下
最好、最坏、平均、均摊时间复杂度：
- 同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度
- 平均时间复杂度：
代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。 - 均摊时间复杂度
两个条件满足时使用：1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂
度；2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。
