time-complexity - 最坏情况与 O(n)

Question

语句“算法 A 的最坏情况运行时间”和“算法 A 的运行时间为 O(n)”之间有区别吗？

我认为“没有区别”，因为最坏的情况是函数可以占用的峰值运行时间，O(n) 表示该函数是“有界的”。两者给出相同的含义。

希望我的逻辑是正确的。

Answer 1

有区别。

算法是 O(f) 并不精确：您必须说算法在其最佳/最差/平均情况下是 O(f)。当最佳、最差和平均值相同时，您可以说是 O(f)，但这并不常见。

Answer 2

我同意你的观点，但是有一些常见的算法（例如快速排序）的预期时间比最坏情况的时间要好得多。你可以声称快速排序是 O(N^2) 最坏的情况，但你仍然希望它几乎总是 O(N*log N) （至少对于一个好的实现来说）。

它还因具有摊销行为的算法而变得复杂。对于一个特定的操作，您可能会得到 O(N) 或 O(log N)，但在摊销意义上，连续的许多操作将始终是 O(1)。张开树和手指树是这一类的好例子。

Answer 3

运行时间作为一个绝对量度通常不如添加更多数据时该时间如何增加重要。例如，一个算法总是需要 5 秒来处理 100 个项目，10 秒来处理 200 个项目等等，被认为是 O(N)，因为运行时间随着数据集大小线性增加。如果第二种算法需要 5*5 = 25 秒来处理这 200 个项目，则它可能被归类为 O(N^2)。这里没有“峰值运行时间”，因为当您向其投入更多数据时，运行时间总是会增加。

事实上，大 O 是一个上限 - 所以你可以说第一个算法也是 O(N^2) （如果 N 是一个上限，N*N 更高，因此也是一个上限，尽管更宽松）。表示其他界限的常用符号包括 Ω（欧米茄，下限）和 Θ（θ，同时下限和上限）。

一些算法（例如，快速排序）根据提供给它的数据表现出不同的行为 - 因此最坏的情况是 O(N^2)，即使它通常表现为 O(N log N)。

Answer 4

这些词串之间存在巨大差异。“算法A的最坏情况运行时间”是一个名词从句，它根本不做任何陈述。“算法 A 的运行时间是 O(n)”是一句话，告诉我们一些关于 A 的事情。