最佳,最差和平均的运行时间

Question

任何人都可以简单地解释一下算法的最佳,最差和平均案例运行时间是什么意思???

Answer 1

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

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

• 最坏的情况 =完成的最慢时间,选择了pessimal输入.
  例如,排序算法的最坏情况可能是以相反顺序排序的数据(但它取决于特定算法).

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

复杂性和运行时间通常以"Big O表示法"表示,其用于描述算法根据其输入的大小完成所需的大致时间量.罗布·贝尔写了一个很好的概括,具有非常明显的例子.

最常用的Big 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