前一篇文章算法复杂度分析（上）讲述了复杂度的大 O 表示法和几个分析原则，这篇文章我们来讲讲另外几种复杂度，最好情况时间复杂度（best case time complexity）、最坏情况时间复杂度（worst case time complexity）、平均时间复杂度（average case time complexity）和均摊时间复杂度（amortized time complexity）。 最好、最坏情况时间复杂度 顾名思义，这两种时间复杂度指的是特殊情况下的时间复杂度。我们看下面的例子： // n 表示数组 array 的长度 int find(int[] array, int ...

为什么需要算法复杂度分析？ 首先，这和研究数据结构和算法的目的有关——“快”而“省”的解决问题。那么如何衡量算法的性能呢？就需要算法复杂度分析。 其次，除了算法复杂度分析，还有一种方法可以衡量复杂度，那就是“事后统计法”，即直接运行程序，统计需要的时间和空间。但是，这种方法有两个问题： 1）结果非常依赖于测试环境。比如，用 Core i3 和用 Core i8 运行程序所需的时间是不同的； 2）结果受测试规模的影响特别大。比如，对有序数组进行排序的时间比对逆序数组排序的时间短；对于小规模数据而言，插入排序所需时间比快速排序要短。 所以，就需要有一种不用具体测试数据，也能估计算法执行效率的方法，...