最坏情况与O(n)

Question

"算法A的最坏情况运行时间"和"算法A的运行时间为O(n)"这两个陈述有区别吗？

我认为它们没有区别，因为最坏情况是函数可能需要的最长运行时间，O(n)表示函数被"限制在"某个范围内。两者的意思相同。

希望我的逻辑是正确的。

- rda3mon

Answer 1

有所差异。

算法的时间复杂度O(f)并不准确：你必须在最好/最坏/平均情况下说明算法的时间复杂度是O(f)。当最好、最坏和平均情况相同时，可以说它是O(f)，但这种情况并不常见。

- Fabio Filippi

---

我认为平均情况和最坏情况具有相同的大O符号是很常见的（例如堆排序、归并排序、基数排序、大多数搜索等）。唯一看到最坏情况与平均情况不同的情况是，如果算法容易受到某些数据集的影响（例如快速排序中的三数取中法）。 - Kendall Hopkins

@KendallHopkins 任何可以调整大小的容器都会给你一个截然不同的最坏情况和平均值。在Java中，ArrayList（Python中的list，Ruby中的Array等类似）提供了分摊的O（1）附加操作，但如果你恰好是触发调整大小的幸运附加操作，你将得到比平均情况慢得多的响应。 - Hank Gay

Answer 2

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

对于具有分摊行为的算法，情况会变得更加复杂。你可能会得到一个特定操作的O(N)或O(log N)，但是连续进行多个操作时，在分摊意义下始终是O(1)。Splay树和Finger树是这一类的好例子。

- xscott

Answer 3

在编程中，运行时间作为绝对度量通常比当你添加更多数据时该时间如何增加不那么重要。例如，一个算法始终需要5秒来处理100个项目，需要10秒来处理200个项目等等，被称为O(N)，因为运行时间随着数据集大小的线性增长而增加。如果第二个算法花费了5*5=25秒来处理这200个项目，它可能被归类为O(N^2)。这里没有“峰值运行时间”，因为当你向其添加更多数据时，运行时间总是增加。

事实上，大O表示上限-因此，您可以说第一个算法也是O(N^2)（如果N是上限，则N*N更高，因此也是上限，尽管是松散的）。用于表示其他上限的常见符号包括Ω（omega，下限）和Θ（theta，同时下限和上限）。

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

- SimonJ

Answer 4

这些单词串之间存在巨大的差异。"算法A的最坏情况运行时间"是一个名词从句，它根本没有陈述任何内容。"算法A的运行时间为O(n)"是一个句子，告诉我们有关A的一些信息。

- Ned Batchelder

---

抱歉，但当问题的标题和正文都犯了同样的“错误”时，我并不认为这是一个笔误。我只是简单地回答了所提出的问题。 - Ned Batchelder

好的。你应该建议他修正措辞，以免像你这样的人困惑。一旦措辞得到修正，你的答案就不太可能再有用了。 - xscott