《数据结构与算法之美--复杂度分析》

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）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。