big-O 表示法是对算法进行最佳、最差和平均情况分析的工具吗？还是 big-O 仅用于最坏情况分析，因为它是一个上限函数？
问问题
5605 次
2 回答
1
它是大 O，因为数量级表示为 O(n)、O(logN) 等。
算法的最佳、最差和平均情况都可以用大 O 表示法表示。
有关应用于排序算法的示例，请参见
http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms
请注意，可以根据多个独立的标准（例如内存使用或 CPU 使用）对算法进行分类。通常，在两个或多个标准之间进行权衡（例如，使用很少 CPU 的算法可能会使用相当多的内存）。
于 2013-01-09T18:09:05.923 回答
1
大“O”是渐近复杂度的度量，也就是说，当 N 变得非常大时，算法大致如何缩放。
如果最好和最差收敛到相同的渐近复杂度，您可以使用单个值 - 或者您可以单独计算它们（例如，某些排序算法在已排序或几乎排序的数据上具有与未排序数据完全不同的特征） .
符号本身并没有传达这一点，但你如何使用它。
...或者大 O 仅用于最坏情况分析...
如果你只给出一个算法的渐近复杂度，它并不能告诉读者最好和最坏情况是否（或如何）与平均值不同。
如果您给出最佳情况和最坏情况的复杂性，它会告诉读者它们有何不同。
默认情况下，如果列出了单个值，则可能是平均复杂度，它可能（或可能不会）与最坏情况收敛。
于 2013-01-09T18:13:02.590 回答