之间的区别是什么O、Ω，Θ?

Question

我学习算法分析。我有麻烦了解之间的差O、Ω，Θ。

他们定义如下：

• f(n) = O(g(n)) 装置 c · g(n) 是一个 上限 f(n).因此存在 一些恒 c 这样， f(n) 是 总是≤ c · g(n), 为足够大的 n (即， n ≥ n0 对于某些恒 n0).
• f(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、Ω，或Θ；为什么不是所有三个?

Answer 1

重要的是要记住符号，无论是O、Ω或Θ，表示 渐进增长的功能;它没有任何东西的本质做的算法 每se.功能有问题 可 是"复杂"(运行时间)的一个算法，要么最糟糕的情况下，最好的情况下，或平均情况，但是表示法是独立的功能。

例如，功能f(n)=3n²+5：

• O(n²)，这也是O(n²记录n),O(n³),O(n⁴)等，但是不O(n)。
• Ω(n²)，它也是Ω(n记录n)、Ω(n)等，但是不Ω(n³).
• Θ(n²).它甚至不是Θ(n²记录n)或Θ(n²/log n)。

现在，通常的功能被认为是最糟糕的情况复杂性的一种算法，这符号的三是使用取决于我们想要什么说它和关于如何小心我们做了分析。例如，我们可以观察到，因为有两种嵌套的循环，最坏的情况下运行的时间 在大多数 O(n²)，而不关心这是否是实际上取得了一些输入。(通常是明显的，它是。) 或者，我们可能会说，最糟糕的情况下运行时间的排序Ω(n记录n)，因为必须有一些投入，为此它必须采取至少cn(记录n)的步骤。或者，我们可以看看一个特定成了归并排序的算法，并看到，它需要在最O(n记录n)步骤在最糟糕的情况 和 这些输入，使得它采取n记录n步骤，使最糟糕的情况下运行的时间是Θ(n记录n)。

请注意，在所有的三个例子上，但是，它仍然相同(最糟糕的情况下)运行时间正在进行分析。我们可以分析最好的情况下，或平均情况相反，但再次表示法的三个我们使用取决于我们所想说的话—我们是否想要给一个上限，下限，或者紧紧束缚在生长 同样的功能.

Answer 2

Θ表示渐紧密的上下限。

O表示一个上限，但是这往可能是、也可能不是紧张。
o表示一个上限，是不是紧张。

Ω表示一个下限，而这往可能是、也可能不是紧张。
ω表示一个下限即不严密。

Answer 3

这些都是一些资源，这将真正帮助你：

• 维基百科
• Wiki书
• 麻省理工学院的讲演视频
• 视频从IITB，印度

Answer 4

为什么这三个的意思是，看看可以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记录n)最糟糕的是，这种泡沫是O(n^2)最糟糕的情况，但O(n)最好的情况下，因为我们不试图全面描述的时间复杂性，我们只是表达的边界，我们关在一个特定的上下文。

在任何情况下，大多数人似乎被延迟，以及不想要的类型希腊字母。我知道我。因此，我们只是说，比较各种是"在最O(n记录n)".这是一个滥用的符号是真的，但它得到的观点。

Answer 5

大O符号是通常被称为复杂的算法，因为它向我们保证，算法将不执行基本上为更多更糟的是为大n.然而，作为是正确指出的那样，此前，大O给了我们渐近的评估和我们的算法行为可能有所不同时，某些输入。例如快速的排序，可O(n^2)，当所列的是已经排序。另一方面，渐近的情况可以改善在实践中有整齐的执行情况。