O、Ω 和 Θ 之间有什么区别？
我正在学习算法分析。我无法理解 O、Ω 和 θ 之间的区别。
它们的定义方式如下：
f(n) = O(g(n))表示c · g(n)是一个f(n)的上限。因此存在 一些常数c使得f(n)是 总是 ≤c · g(n)，对于足够大的n（即对于某个常数n0，n ≥ n0）。f(n) = Ω(g(n))表示c · g(n)是f(n)的下界。因此存在 一些常数c使得f(n)是 对于所有n ≥ n0，始终 ≥c · g(n)。f(n) = θ(g(n))表示c1 · g(n)是f(n)的上限 code> 和c2·g(n)是 对于所有n ≥ n0，f(n)的下界。 因此存在常量c1和c2使得 f(n) ≤ c1 ·g(n) 且 f(n) ≥ c2·g(n)。这意味着g(n)为f(n)提供了一个很好的、紧密的界限。
我的理解方式是：
O(f(n))给出给定函数/算法的最坏情况复杂性。Ω(f(n))给出给定函数/算法的最佳情况复杂性。θ(f(n))给出给定函数/算法的平均情况复杂度。
如果我错了，请纠正我。如果是这种情况，每个算法的时间复杂度必须用所有三种符号表示。但我观察到它被表示为 O、Ω 或 θ；为什么不是全部三个？
I am learning algorithm analysis. I am having trouble understanding the difference between O, Ω, and Θ.
The way they're defined is as follows:
f(n) = O(g(n))meansc · g(n)is an
upper bound onf(n). Thus there exists
some constantcsuch thatf(n)is
always ≤c · g(n), for large enoughn
(i.e.,n ≥ n0for some constantn0).f(n) = Ω(g(n))meansc · g(n)is a
lower bound onf(n). Thus there exists
some constantcsuch thatf(n)is
always ≥c · g(n), for alln ≥ n0.f(n) = Θ(g(n))meansc1 · g(n)is an upper bound onf(n)andc2 · g(n)is a
lower bound onf(n), for alln ≥ n0.
Thus there exist constantsc1andc2
such thatf(n) ≤ c1 ·g(n)andf(n) ≥. This means that
c2 ·g(n)g(n)
provides a nice, tight bound onf(n).
The way I have understood this is:
O(f(n))gives worst case complexity of given function/algorithm.Ω(f(n))gives best case complexity of given function/algorithm.Θ(f(n))gives average case complexity of given function/algorithm.
Please correct me if I am wrong. If it is the case, time complexity of each algorithm must be expressed in all three notations. But I observed that it's expressed as either O, Ω, or Θ; why not all three?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
重要的是要记住，符号，无论是 O、Ω 还是 θ，都表示函数的渐近增长；它本质上与算法本身没有任何关系。所讨论的函数可能是算法的“复杂性”（运行时间），无论是最坏情况、最好情况还是平均情况，但符号与函数的来源无关。
例如函数f(n)=3n2+5是：
现在，通常考虑的函数是算法的最坏情况复杂性，使用这三种符号中的哪一种取决于我们想要表达的内容以及我们进行分析的仔细程度。例如，我们可能会观察到，由于有两个嵌套循环，最坏情况的运行时间最多 O(n2)，而不关心这是否实际上是实现了一些输入。 （通常很明显确实如此。）或者，我们可以说排序的最坏情况运行时间是 Ω(n log n)，因为必须有一些输入至少需要 cn(log n)步骤。或者，我们可以查看特定的归并排序算法，并发现在最坏的情况下最多需要 O(n log n) 步并且某些输入使其需要 n log n 步，所以最坏情况下的运行时间是 θ(n log n)。
请注意，在上面的所有三个示例中，分析的运行时间仍然相同（最坏情况）。我们可以分析最佳情况或平均情况，但同样，我们使用这三种表示法取决于我们想要表达的内容——我们是否想要给出一个上限、下界或紧界相同功能的增长。
It is important to remember that the notation, whether O, Ω or Θ, expresses the asymptotic growth of a function; it does not have anything intrinsically to do with algorithms per se. The function in question may be the "complexity" (running time) of an algorithm, either worst-case, best-case or average-case, but the notation is independent of where the function comes from.
For example, the function f(n)=3n2+5 is:
Now, usually the function considered is the worst-case complexity of an algorithm, and which notation of the three is used depends on what we want to say about it and on how carefully we do the analysis. For example, we may observe that because there are two nested loops, the worst-case running time is at most O(n2), without caring about whether this is actually achieved for some input. (Usually it is obvious that it is.) Or, we may say that the worst-case running time of sorting is Ω(n log n), because there must be some inputs for which it must take at least cn(log n) steps. Or, we may look at a particular mergesort algorithm, and see that it takes at most O(n log n) steps in the worst-case and that some input makes it take n log n steps, so the worst-case running time is Θ(n log n).
Note that in all the three examples above, it was still the same (worst-case) running time that was being analyzed. We may analyze the best-case or average-case instead, but again, which notation of the three we use depends on what we want to say — whether we want to give an upper bound, lower bound, or tight bound on the order of growth of the same function.
θ 表示渐进紧的上限和下限。
O 表示上限，但这个界限可能很紧，也可能不紧。
o 表示不紧的上限。
Ω 表示下限，但该界限可能很紧，也可能不紧。
ω 表示不严格的下界。
Θ denotes an asymptotically tight upper and lower bound.
O denotes an upper bound, but this bound might or might not be tight.
o denotes an upper bound that is not tight.
Ω denotes a lower bound, but this bound might or might not be tight.
ω denotes a lower bound that is not tight.
对于这三个的含义，请参阅 Can Berk Güder 的回答。
另请注意，它们与最佳情况、最坏情况和平均情况完全无关。例如，冒泡排序是 θ(n) 最好情况（因为如果数据已经排序，则只需要 n-1 次比较），最坏情况是 θ(n^2)。假设随机打乱输入，则平均情况为 θ(n^2)。因此，平均情况也是 O(n^2)、O(n^3) 和 O(2^n)。
所以，O、θ 和 Ω 告诉你它是什么样的界限。他们不会告诉您界限是什么。在上下文中，它可能是对最好情况、最坏情况、平均情况或整个算法（所有情况）的限制。
当然，如果算法的最佳情况为 Ω(g)，那么它本身就是 Ω(g)。如果最坏情况是 O(g)，那么它就是 O(g)。所以那里有一种关系。但如果它的平均情况为 θ(g)，则几乎无法告诉您有关最佳情况和最坏情况的信息。
至于“为什么三个都不行？”。
如果你的函数是 θ(g)，那么它也是 O(g) 和 Ω(g)。因此，除了 θ 边界之外，提供其他边界并没有多大意义。
当你单独看到其他一个时，通常是因为我们只关心上限，或者我们只关心下限。所以我们说所有比较排序都必然是 Ω(n log n) 最坏情况，冒泡排序是 O(n^2) 最坏情况，但 O(n) 最好情况，因为我们并没有试图完全描述时间复杂性，我们只是表达我们在特定上下文中关心的界限。
无论如何，大多数人似乎都很懒，不想输入希腊字母。我知道我是。所以我们只是说比较排序“最多是 O(n log n)”。这确实是对符号的滥用，但它表达了要点。
For what those three mean, see Can Berk Güder's answer.
Note also that they have nothing at all to do with best case, worst case, and average case. Bubble sort for example is Θ(n) best case (because if the data is already sorted, only n-1 comparisons are needed), and Θ(n^2) worst case. It's Θ(n^2) average-case assuming randomly-shuffled input. That average case therefore is also O(n^2), and O(n^3), and O(2^n).
So, O, Θ and Ω tell you what kind of bound it is. They don't tell you what the bound is a limit on. In context, it might be a limit on the best case, the worse case, the average case, or the algorithm as a whole (all cases).
Of course if an algorithm has Ω(g) best case, then it is itself Ω(g). If it has O(g) worst case it is O(g). So there is a relation there. But if it has Θ(g) average case, that tells you almost nothing about the best and worst cases.
As for "why not all three?".
If your function is Θ(g), then it is also O(g) and Ω(g). So there's not much point providing other bounds alongside a Θ bound.
When you see one of the others alone, it's generally because we only care about an upper bound, or we only care about a lower bound. So we say that all comparison sorts are necessarily Ω(n log n) worst case, and that bubble sort is O(n^2) worst case but O(n) best case, because we aren't trying to fully describe the time complexity, we're just expressing the bounds we care about in a particular context.
And in any case most people seem to be lazy, and don't want to have to type Greek letters. I know I am. So we just say that comparison sorts are "at best O(n log n)". It's an abuse of notation really, but it gets the point across.
这些是一些真正对您有帮助的资源：
These are some of the resources that will really help you:
Big-O 表示法通常被称为算法的复杂性，因为它向我们保证，对于较大的 n，算法的性能不会明显变差。然而，正如之前正确指出的那样，Big-O 为我们提供了渐近评估，并且当给定某些输入时，我们的算法可能表现不同。例如，当数组已经排序时，快速排序可以是 O(n^2)。 OTOH，通过巧妙的实施，渐近情况可以在实践中得到改善。
Big-O notation is often referred to as complexity of an algorithm because it assures us, that the algorithm will not perform substantially more worse for large n. However, as was rightly pointed out earlier, the Big-O gives us the asymptotic evaluation and our algorithm may behave differently when certain input is given. For example quick sort can be O(n^2), when the array is already sorted. OTOH, asymptotic situation may be improved in practice with neat implementation.
最好的情况用 Ω(n) 表示法表示。
最坏的情况用 Ο(n) 表示法表示。
平均情况用 θ(n) 符号表示。
Best case is represented by Ω(n) notation.
Worst case is represented by Ο(n) notation.
Average case is represented by Θ(n) notation.