O，Ω和Θ有什么区别？
我正在学习算法分析。我无法理解O，Ω和Θ之间的差异。
定义它们的方式如下：
f(n) = O(g(n))表示c · g(n)的上限f(n)。因此，存在足够大的常量（即对于某些常量），
c该常量f(n)始终为≤ 。c · g(n)``n``n ≥ n0``n0f(n) = Ω(g(n))表示c · g(n)的下限f(n)。因此存在一些常数c，从而f(n)始终≥c ·，对所有g(n)
n ≥ n0。f(n) = Θ(g(n))均值c1 · g(n)是所有人的上限f(n)和c2 · g(n)下限。因此存在常数和使得和。这意味着在上 提供了一个很好的紧密边界。
f(n)``n ≥ n0``c1``c2``f(n) ≤ c1 ·g(n)``f(n) ≥ c2·g(n)``g(n)``f(n)
我了解的方式是：
O(f(n))给出给定功能/算法的最坏情况下的复杂性。Ω(f(n))给出给定功能/算法的最佳情况复杂度。Θ(f(n))给出给定功能/算法的平均大小写复杂度。
如果我错了，请纠正我。如果是这样，则每种算法的时间复杂度必须用所有三种表示法表示。但我观察到它表示为O，Ω或Θ。为什么不全部三个？
回答：
重要的是要记住，无论是O，Ω还是Θ，该符号都表示 的 。它 本身 与算法 本身 没有任何关系。所讨论的功能 可能
是算法的“复杂性”（运行时间），无论是最坏情况，最佳情况还是平均情况，但是表示法与功能的来源无关。
例如，函数f（n）= 3n 2 +5为：
- O（n 2），它也是O（n 2 log n），O（n 3），O（n 4）等，但不是O（n）。
- Ω（n 2），它也是Ω（n log n），Ω（n）等，但不是Ω（n 3）。
- Θ（n 2）。它甚至不是Θ（n 2 log n）或Θ（n 2 / log n）。
现在，通常考虑的功能是算法的最坏情况下的复杂性，使用这三种表示法取决于我们要说的是什么以及我们进行分析的认真程度。例如，我们可能会观察到，由于存在两个嵌套循环，因此最坏情况下的运行时间
最多为 O（n 2），而不关心是否对于某些输入实际上可以实现。（通常很明显是这样。）或者，我们可以说排序的最坏情况下的运行时间是Ω（n log
n），因为必须有一些输入至少要使用cn（log n）脚步。或者，我们可以看一个具体的归并算法，并看到它需要至多为O（n log n）的在最坏的情况下，步骤
和 某些输入使它花了n log n步，因此最坏的运行时间是Θ（n log n）。
请注意，在以上所有三个示例中，所分析的运行时间仍然是相同的（最坏情况）。我们可以改为分析最佳情况或平均情况，但同样，我们使用的三种表示形式取决于我们要说的内容-
我们是否要按以下顺序给出上限，下限或严格限增长 相同的功能 。
以上是 O，Ω和Θ有什么区别？ 的全部内容， 来源链接： utcz.com/qa/428039.html
