最坏情况与 O(n)
“算法 A 的最坏情况运行时间”和“算法 A 的运行时间为 O(n)”之间有区别吗？
我认为“没有区别”，因为最坏的情况是函数可以花费的峰值运行时间，O(n) 意味着函数“有界”。两者赋予相同的含义。
希望我的逻辑是正确的。
Is there a difference between statement "Worst case running time of an Algorithm A" and "Running time of an Algorithm A is O(n)"?
What I think "there is no difference" because, worst case is the peak running time that the function can take, O(n) means that the function is "bounded by". Both give the same meaning.
Hope my logic is correct.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
有差别。
O(f) 的算法并不精确：你必须说在最佳/最差/平均情况下，算法是 O(f) 。当最好、最差和平均值相同时，您可以说这是 O(f)，但这并不常见。
There is difference.
An algorithm is O(f) is not precise: you must say an alogirthm is O(f) in its best/worst/avarage case. You can say that is O(f) when best, worst and avarage are the same, but that's not so common.
我同意你的观点，但有一些常见的算法（例如快速排序）的预期时间比最坏情况下的时间要好得多。你可以声称快速排序是 O(N^2) 最坏的情况，但你仍然期望它几乎总是 O(N*log N) （至少对于一个好的实现来说）。
具有摊销行为的算法也会变得复杂。对于一个特定的操作，您可能会得到 O(N) 或 O(log N) 的复杂度，但从摊销的意义上来说，连续的许多操作将始终是 O(1) 。八字树和手指树是此类别的很好的例子。
I agree with your sentiment, but there are common algorithms (quicksort for instance) that have an expected time much better than their worst case time. You could claim quicksort is O(N^2) worst case, but you still expect it to be O(N*log N) almost always (at least for a good implementation).
It also gets complicated with algorithms that have amortized behavior. You might get O(N) or O(log N) for one particular operation, but many operations in a row will always be O(1) in the amortized sense. Splay trees and Finger trees are good examples in this category.
作为绝对衡量标准的运行时间通常不如添加更多数据时时间增加的情况重要。例如，处理 100 个项目总是需要 5 秒，处理 200 个项目需要 10 秒等等的算法被认为是 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)。
Running time as an absolute measure is usually less important than how that time increases when you add more data. For example, an algorithm that always takes 5 seconds to process 100 items, 10 seconds to process 200 items and so on, is said to be O(N) since the running time increases linearly with the dataset size. If a second algorithm took 5*5 = 25 seconds to process those 200 items instead, it might be classed as O(N^2). There's no "peak running time" here, since the running time always increases when you throw more data at it.
In fact, big O is an upper bound - so you could say the first algorithm was O(N^2) as well (if N is an upper bound, N*N is higher and hence also an upper bound, albeit a looser one). Common notation to denote other bounds includes Ω (omega, lower bound) and Θ (theta, simultaneous lower and upper bound).
Some algorithms (for instance, Quicksort) exhibit different behaviour depending on the data fed to it - hence the worst case is O(N^2) even though it usually behaves as if it were O(N log N).
那一串串单词之间有着巨大的差异。 “算法 A 的最坏情况运行时间”是一个名词从句，它根本没有任何陈述。 “算法 A 的运行时间为 O(n)”这句话，告诉我们关于 A 的一些事情。
There is a huge difference between those strings of words. "Worst case running time of an Algorithm A" is a noun clause, it makes no statement at all. "Running time of Algorithm A is O(n)" is a sentence, telling us something about A.