时间戳

首页 > 解决方案 > 进一步简化并找到 c1 和 c2 (Big Theta)

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

问题描述

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

这是我已经走了多远：

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

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

谢谢。

标签： algorithmmath

解决方案

对于某些 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

那么 limit 的定义告诉你有 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) 的启发式方法，然后通过计算上述限制来验证它是否可以工作。

还要注意链接中表格中关于限制定义的列。这些限制（或 limsups）的值告诉您在正式定义中使用哪些常量。

审查限制：

记住极限的定义

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)

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

推荐阅读