您好，我已尽力理解 big-theta，现在我得到了 Big-Oh 和 Big-Omega 证明的主要概念，但我找不到与我的练习相近的示例，因为我做不到证明：
通过展示证人证明 4n^2 + 4n = Big-Theta(2n^2 + 32n)
我知道我必须为 Big-Oh 和 Big-Omega 证明它才能证明 Big-Theta，但我不知道如何开始。我的意思是右边的等式让我感到困惑。
问问题
19724 次
1 回答
4
根据big-theta 的定义，您需要证明存在两个常数 k1 和 k2，这样对于所有足够大的 n 值，
k1 * |2n^2 + 32n| <= |4n^2 + 4n| <= k2 * |2n^2 + 32n|
（因为你的函数对于正 n 都是正的，你可以去掉绝对值。）只要证明每个不等式都可以单独满足，你就完成了。
于 2011-03-28T20:50:41.393 回答