算法基础

1.时间复杂度

1. 最好情况时间复杂度：代码在最理想情况下执行的时间复杂度。

2. 最坏情况时间复杂度：代码在最坏情况下执行的时间复杂度。

3. 平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。

4. 均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

• 求解算法的时间复杂度的具体步骤

  • ⑴ 找出算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
  • ⑵ 计算基本语句的执行次数的数量级；
  • ⑶ 用大 Ο 记号表示算法的时间性能。

• 分析一段代码的时间复杂度的三个方法

  • 只关注循环执行次数最多的的一段代码
  • 加法法则：总复杂度等于量级最大的那段代码的复杂度
  • 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积