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

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

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

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

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

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

复杂性和运行时间通常用“Big O 表示法”来表示，它用于根据输入的大小来描述算法完成所需的大致时间量。罗布·贝尔写了一篇优秀的概述 http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/有非常清楚的例子。

最常用的 Big O 描述是

• O(1)无论输入大小如何，总是在大约相同的时间内终止。
• O(logN)每次输入大小加倍时，都会花费固定的额外时间。
• O(N)如果输入大小加倍，则需要两倍的时间才能完成。
• O(N²) takes four times as long if the input size doubles.
• O(2^N) increases exponentially as the input size increases.

从下表中您可以看到，对于较小的输入大小，差异很小，但当输入大小增加一点点时，差异就会变得巨大。

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