第二节 基本概念

要点

• 时间复杂度
• 空间复杂度

1.1 时间复杂度

• 代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。
• 大O表示法只关注n的最高阶；也就是说：分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了

计算规则

• 1. 只关注循环执行次数最多的一段代码
• 2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
     如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n)))
• 3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
     ``
     如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)*g(n))

• 最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度

• 最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度

• 平均情况时间复杂度：

• 加权平均时间复杂度

• 均摊时间复杂度

``

1.2 空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。