如何准确区分最好、最坏、平均、均摊时间复杂度？

本文共计4149个文字，预计阅读时间需要17分钟。

上一节，我们介绍了复杂度表示法和几个分析技巧，还列举了一些常见复杂度分析的例子，如O(1)、O(logn)、O(n)、O(nlogn)等。掌握了这些内容，对复杂度分析这个知识点就有了基本的了解。

上一节，我们讲了复杂度的大 O表示法和几个分析技巧，还举了一些常见复杂度分析的例子，比如 O(1)、O(logn)、O(n)、O(nlogn) 复杂度分析。掌握了这些内容，对于复杂度分析这个知识点，你已经可以到及格线了。但是，我想你肯定不会满足于此。

今天我会继续给你讲四个复杂度分析方面的知识点，最好情况时间复杂度（best case time complexity）、最坏情况时间复杂度（worst case time complexity）、平均情况时间复杂度（average case time complexity）、均摊时间复杂度（amortized time complexity）。如果这几个概念你都能掌握，那对你来说，复杂度分析这部分内容就没什么大问题了。

最好、最坏情况时间复杂度

上一节我举的分析复杂度的例子都很简单，今天我们来看一个稍微复杂的。你可以用我上节教你的 分析技巧，自己先试着分析一下这段代码的时间复杂度。