数据结构&算法

在分析算法效率时，经常关注以下两种复杂度：

（1）最坏情况复杂度：T_worst(n)

（2）平均复杂度：T_avg(n)

易知T_avg(n)<=T_worst(n)

注：一般分析最坏情况复杂度，因为平均复杂度不容易找

下表能够比较直观的看出各个复杂度的运行时间

所以一般情况下避免出现后两种复杂度

下图是几种复杂度的增长速度

（图片来自慕课，陈越姥姥那堂课）

复杂度分析的窍门：

1. 若已知T₁(n) = O(f₁(n))和T₂(n) = O(f₂(n))，则
   T₁(n) + T₂(n) = max(O(f₁(n)),O(f₂(n)))  （就是O(f₁(n))和O(f₂(n))的最大值）
   T₁(n) × T₂(n) = O(f₁(n) × f₂(n))
2. for循环的T(n) = 循环次数 × 循环体代码的复杂度
3. if-else结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中的最大值

 2020-03-19

数据结构&算法

原文：https://www.cnblogs.com/LeeJD/p/12524855.html