像 f(n)=3n^2+2 这样的函数是 O(n^2) 因为 n^2 是函数中的最大指数。但是，函数 1f(n)= n^31 不是 O(n^2) 因为最大的指数是 3，而不是 2。
因此，为了对 Big Omega 或 Big Theta 做出这样的猜测，我们应该在函数中寻找什么？我们可以做一些类似于我们为上面的大 O 表示法所做的事情吗？
例如，假设问题要求我们找到函数 f(n)= 3n^2 +1 的 Big Omega 或 Big Theta。是 f(n)= O(n)、Big Omega(n) 还是 Big Theta(n)？如果我要对这个函数是否是大 O(n) 进行有根据的猜测，我会说不是(因为函数的最大指数是 2，而不是 1)。我会使用归纳法更正式地证明这一点。
那么，我们可以做一些类似于我们在第一个示例中使用大 O 表示法所做的事情吗？我应该在函数中寻找什么来猜测 Big Omega 和 Theta 是什么，并确定“有根据的猜测”是否正确？
最佳答案
你的例子使用了多项式，所以我会假设。
如果 k 大于或等于多项式的阶数，则您的多项式为 O(n^k)。
如果 k 小于或等于多项式的阶数，则您的多项式为 Omega(n^k)。
如果多项式是 O(n^k) 和 Omega(n^k)，则它是 Theta(n^k)。
关于algorithm - 大欧米茄和大西塔，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47503526/