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）。

请注意，在以上所有三个示例中，所分析的运行时间仍然是相同的（最坏情况）。我们可以改为分析最佳情况或平均情况，但同样，我们使用的三种表示形式取决于我们要说的内容-
我们是否要按以下顺序给出上限，下限或严格限增长 相同的功能 。