algorithm - 算法的最佳、最差和平均情况运行时间是多少？

Question

算法的最佳、最差和平均情况运行时间是多少？

Answer 1

用最简单的术语来说，对于输入大小为 n 的问题:

• 最佳情况 = 最快完成时间，选择最佳输入。
  例如，排序算法的最佳情况是已经排序的数据。

• 最坏情况 = 完成时间最慢，选择的输入不多。
  例如，排序算法的最坏情况可能是数据以相反的顺序排序(但这取决于特定算法)。

• 平均情况 = 算术平均值。多次运行该算法，使用许多大小为 n 的不同输入，这些输入来自生成这些输入的某个分布(在最简单的情况下，所有可能的输入都有相同的可能性)，计算总运行时间(通过添加个人时间)，并除以试验次数。您可能还需要根据输入集的大小对结果进行归一化。

复杂性和运行时间通常用“大 O 表示法”表示，它用于根据输入的大小描述算法完成所需的大致时间。 Rob Bell 写了一篇 excellent overview有非常清楚的例子。

最常用的大O描述是

• O(1) 总是在大致相同的时间内终止，无论输入大小如何。
• O(logN) 每次输入大小加倍时都会花费固定的额外时间。
• O(N) 如果输入大小加倍，则需要两倍的时间才能完成。
• O(N²) 如果输入大小加倍，则需要四倍的时间。
• O(2^N) 随着输入大小的增加呈指数增长。

您可以从下表中看出，对于较小的输入大小，差异很小，但随着输入大小的增加，即使增加一点点，差异也会变得很大。

Input Size              Time to Complete               O(1)  O(logN)   O(N)   O(N2)   O(2N)     1           1       1      1       1       1     2           1       2      2       4       4     4           1       3      4      16      16     8           1       4      8      64     256    16           1       5     16     254   65536