big-theta - 如何确定函数 f 是否在 theta(g) 中

Question

完全披露：这是一个家庭作业问题。老实说，当它看起来如此简单时，它却躲避了我这么久，我真的有点害怕。

好的，问题是，f(n) = n^2*log(n), g(n) = n^2.1。f 在 theta(g) 中吗？

我只需要想出常数 c ₁ , c ₂以便超过某个 n ₀ , f(n) <= c ₁ g(n) <= c ₂ f(n)。但我什至不确定 f 是否在 theta(g) 中。我很困惑。

Answer 1

据我所知，要证明 f(n) 在 theta(g(n)) 中，您可以采用两种不同的方法：

1. 证明 f 在 O(g) 中并证明 g 在 O(f) 中。

2. 证明 f 在 O(g) 中并证明 f 在 BigOmega(g) 中。

Answer 2

首先注意措辞。“在 theta(g) 中是 f”。这意味着他们希望您首先对它是否属实做出有根据的猜测。

反问：theta(n) 和 theta(n * log(n)) 一样吗？我们知道那个答案……不，它们不是（例如，基于比较的排序将是线性的）。这对您的问题有什么建议？

为了证明这一说法，请遵循 MahlerFive 的另一个答案。为了完整起见，为了试图反驳这一说法，假设敌人提出了常数 c1 和 c2。现在我们的目标是表明，尽管敌人出现了哪些常数（即对于所有 c1 和 c2），但没有 n0 满足边界。换句话说，表明你没有办法选择c1和c2。在您的情况下，技巧可能以 f 函数中的 log(n) 因子为中心。log(n) 是单调递增的，这表明我们可以通过插入更大的 n 值来使该因子任意大。

我希望这能让你在继续自己解决问题的同时仍然感到满意。如果我完全错了，我相信其他读者会纠正我的。