数据结构与算法之美笔记 : 浅析最好、最坏、平均、均摊时间复杂度

 

 

 

最好情况时间复杂度（best case time complexity)

 

最好情况是，数组第一个元素就是要找的变量x，此时的时间复杂度为O(1)，即最好情况时间复杂度。

 

 

 

 

最坏情况时间复杂度（worst case time complexity)

 

最坏情况是，要遍历完整个数组，此时的时间复杂度为O(n)，即最坏情况时间复杂度。

 

 

 

 

 

 

 

 

 

平均情况时间复杂度（average case time complexity)

 

这个值是概率论中的加权平均值，也叫期望值。

所以，平均时间复杂度的全称应该叫加权平均时间复杂度或期望时间复杂度。

 

上面的代码的加权平均值为(3n+1)/4，用大O表示法表示，去掉系数和常量，加权平均时间复杂度是O(n)。

 

在大多数情况下，我们并不需要区分最好、最坏、平均情况时间复杂度。

 

一般情况下，我们使用一个复杂度就可以了。

 

只有同块代码在不同的情况下，时间复杂度有量级的差距，

才会使用这三种复杂度表示法来区分。

 

 

均摊时间复杂度（amortized time complexity)

 

针对这种特殊的场景，采用更简单的分析方法：摊还分析法。这分析方法是将高级别复杂度均摊到低级别复杂度中，得到的时间复杂度叫，均摊时间复杂度。

 

常用的应用场景：

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系。这时，可以将这一组操作放在一起分析，看能否将较高时间复杂度的操作的耗时，平摊到时间复杂度较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好时间复杂度。

 

均摊时间复杂度可以认为是一种特殊的平均时间复杂度，但在实际运用中，不用特意区别它们。分析得到的结果叫平均或均摊，只是个说法，并不重要。

 

总结:

 

 

一、复杂度分析的4个概念
1.最坏情况时间复杂度：代码在最理想情况下执行的时间复杂度。
2.最好情况时间复杂度：代码在最坏情况下执行的时间复杂度。
3.平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。
4.均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

二、为什么要引入这4个概念？
1.同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，所以引入这4个概念。
2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下，是不需要区别分析它们的。

三、如何分析平均、均摊时间复杂度？
1.平均时间复杂度
代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。
2.均摊时间复杂度
两个条件满足时使用：1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度；2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

 

 

 

 

来源:

数据结构与算法之美   -- 王争