算法分析-渐近分析

Question

大家好，我已经开始学习算法分析了。这里我对渐近分析有疑问。假设我有一个函数 f(n) = 5n^3 + 2n^2 + 23。现在我需要为上述函数找到 Big-Oh、Big-Omega 和 Theta 符号，

Big-Oh: 
    f(n) <= (5 + 2 + 23) n^3  // raising all the n's to the power of 3 will give us a value which will be always greater than f(n)
    f(n) <= 30n^3
    f(n) belongs to Big-Oh(n^3)

Big-Omega:
    n^3 <= f(n)
    f(n) belongs to Big-Omega(n^3)

Theta: 
    n^3 <= f(n) <= 30 n^3 
    f(n) belongs to Theta ( n^3)
So here, 
    f(n) belongs to Big-Oh(n^3)
    f(n) belongs to Big-Omega(n^3)
    f(n) belongs to Theta(n^3)

像这样对于任何多项式，Oh、Omega 和 Theta 符号的增长顺序是相同的(在我们的例子中是 n^3 的顺序)。当所有符号的增长顺序相同时，用不同的符号显示它们有什么用，以及确切的位置可以用吗？如果可能的话，请给我一个实际的例子。

Answer 1

Big theta (Θ) 是当我们的上限 (O) 和下限 (Ω) 相同时，换句话说，它是一个紧密的界限。这就是同时显示 O 和 Ω(或者三个)的原因之一。

为什么这有用？因为 Θ 是一个紧界 - 它比 O 强得多。使用 O 你可以说上面是 O(n^1000) 并且你在技术上仍然是正确的。很多时候 O != Ω 并且您没有那么严格的约束。

那为什么我们经常谈论 O 呢？好吧，因为在大多数情况下，我们对算法的上限(最坏情况)感兴趣。有时我们根本不知道 Θ 而用 O 代替。同样重要的是要注意，许多人只是误用了这些符号，没有完全理解它们和/或只是不够精确，并在可能是 Θ 的地方使用了 O用过。

例如，快速排序没有严格的界限(除非我们专门讨论最佳/平均或最坏情况分析)，因为它在最佳和平均情况下为 Ω(nlogn)，但在最坏情况下为 O(n^2)案件。另一方面，合并排序既是 Ω(nlogn) 又是 O(nlogn)，因此它也是 Θ(nlogn)。

总而言之，这都是理论上的，因为实践中的快速排序在大多数情况下更快，因为您通常不会遇到最坏的情况，而且快速排序完成的操作更容易。