algorithm - 进一步简化并找到 c1 和 c2 (Big Theta)

Question

我正试图找到 c1 和 c2，但在继续进行时遇到了一些困难。

这是我得到的结果:

(21n^2 + 97n + 26) (log(1024n^2 + 100)) ∈ θ(n^2 log n)

不确定如何进一步扩展它并获得我的 c1 和 c2。

谢谢。

Answer 1

对于某些 epsilon > 0 和 epsilon < 21*2，您可以将 c1 和 c2 取为 21*2 + epsilon 和 21*2 - epsilon。由于许多值都有效，因此请选择一个。例如epsilon = 1 就满足要求。因此，您可以将 43 和 41 作为常数因子。

为了证明这些可以工作，你计算了

(21n^2 + 97n + 26) (log(1024n^2 + 100)) / (n^2ln(n)) --> 21*2

然后极限的定义告诉你有 N，这取决于你选择的 epsilon，这样对于所有 n > N，你将有 21*2 - epsilon 和 21*2 + epsilon 之间的商。因此，

(21*2 - epsilon) n^2ln(n) <= (21n^2 + 97n + 26) (log(1024n^2 + 100)) <= (21*2 + epsilon)n^2ln( n)

对于所有 n > N。

---

人们所做的并不是进一步扩展，而是删除无关紧要的术语

21n^2ln(1024n^2)

进一步

21*2n^2ln(n)

请注意如何根据 ln(1024n^2)=2ln(n)+ln(1024) 去除 1024。

整个归约并不是正式的证明，只是一种启发式方法来获得候选值 21*2n^2ln(n)，然后通过计算上述限制验证其是否有效。

---

另请注意 link that you were given 中表中有关限制定义 的列.这些限制(或限制)的值告诉您在正式定义中使用哪些常量。

---

限制审查:

请记住 definition of limit

lim F(n) = a

是对于所有 epsilon > 0 存在 N 使得对于所有 n > N 你将拥有

a - epsilon <= F(n) <= a + epsilon

如果 F(n) 是分数 f(n)/g(n) 就像我们上面的分数，那么这个不等式意味着

(a - epsilon)g(n) <= f(n) <= (a + epsilon)g(n)

这就是极限的定义如何与不等式中的常数相关。