algorithm - 何时何地使用哪种渐近符号

Question

我已经通过这个 Big-Oh 的解释，了解了两个循环的复杂性， big theta 和 big-oh 之间的区别，也通过了这个问题。

我知道我们不能说 Big-oh 是最坏的情况，Omega 是最好的情况，而 theta 是平均情况。Big-oh 有自己的最佳、最差和平均情况。但是我们如何发现任何特定算法都属于 Big-oh、Big-theta 或 Big-Omega。或者我们如何检查是否有任何算法属于所有这些。

标签： algorithmtime-complexitybig-ocomputer-sciencecomplexity-theory

Answer 1

函数 f(n) 是函数 g(n) 的 Big-Oh，写为 f(n) = O(g(n))，如果存在正常数 c 和自然数 n0 使得对于 n > n0 , f(n) <= c * g(n)。函数 f(n) 是 g(n) 的 Big-Omega，写作 f(n) = Omega(g(n))，当且仅当 g(n) = O(f(n))。函数 f(n) 是函数 g(n) 的 Theta，写作 f(n) = Theta(g(n))，当且仅当 f(n) = O(g(n)) 和 f(n ) = 欧米茄 (g(n))。

为了证明任何免费，您可以通过展示一些功能是其他一些功能的 Big-Oh 来做到这一点。在一般情况下，要证明一个函数是另一个函数的 Big-Oh 是一个难题。任何形式的数学证明都可能有所帮助。与基本案例的直觉相结合的归纳证明并不少见。基本上，猜测 c 和 n0 的值，看看它们是否有效。其他选项包括选择两者中的一个并为另一个计算出合理的值。

请注意，一个函数可能不是任何其他函数的 Big-Theta，如果其从上方和下方的最紧密边界是具有不同渐近增长率的函数。但是，我认为通常可以肯定的是，大多数函数都将是相当简单的 Big-Oh，并且通常从这个角度看待的所有函数在最好的情况下至少是恒定时间的 - Omega(1)。