big-o - 渐近分析不等式

Question

我很难理解以下以红色突出显示的不等式是如何针对这个渐近分析问题得出的。有人可以解释这些不平等的性质以及它们是如何形成的吗？

下图有问题和解决方法。以红色突出显示的部分是我无法理解的地方。

问题及解决方案图片

Answer 1

准备工作

上图中红色标记部分上方的部分是 Big-Θ 符号的定义：“ f(n)in Θ(g(n))”，其中

f(n) = (n + a)^b, b > 0        (+)
g(n) = n^b                     (++)

当显示它在下面成立时，我们将重复这个不等式以简化引用：

f(n) is in Θ(g(n)) with f(n) and g(n) as in (+) and (++), respectively

  <=>

c_1⋅n^b ≤ (n + a)^b ≤ c_2⋅n^b, for some positive constants c_1, c2     (*)
                               for n ≥ n_0, with n_0 constant > 0

因此，我们想找到一些c_1，c_2并且n_0这样(*)成立。

---

解决方案（详细解释）

现在，因为b > 0，如果以下两个不等式成立，我们可以证明(*)成立：

n + a ≥ k_1⋅n, for n > n_0      (i)
n + a ≤ k_2⋅n, for n > n_0      (ii)

对于一些正常数k_1and k_2（分别与c_1和c_2ask_1^b = c_1和相关k_2^b = c_2）。

显示(ii)成立

我们将首先证明它(ii)适用于某个正常数k_1。为此，我们可以自由选择 n_0（n_0 ≥ |a|因为a只是一个常数）。

=> n ≥ |a| ≥ a, since n ≥ n_0 ≥ |a|

Hence:

n + a ≤ n + |a| ≤ n + n = 2⋅n, for n ≥ n_0 ≥ |a|   (II)

现在，(II)我们已经证明了(ii)成立，k_1 = 2并且n_0是任何大于abs(a),的值n_0 ≥ |a|。

显示(i)成立

现在展示(i)：我们首先注意到以下不等式始终成立：

n + a ≥ n - |a|                  (†)

a（如果是负数，实际上是相等）。现在，从上面回忆一下(II)适用于任何n_0 ≥ |a|. 好吧，让我们选择修正我们的n0at 2⋅|a|（再次注意：我们可以自由选择我们想要证明不等式(*)成立的常数）。

Choose n_0 as n_0 = 2⋅|a|        (††)

因此，从(†)：

n + a ≥ n - |a| ≥ n - n/2 = n/2  (†††)
                ^
                | 
               Why? Since from (††): |a| = n_0/2 < n/2, since n>n_0

We repeat (†††) without the middle stuff:  

n + a ≥ (1/2)⋅n, for n > n_0 = 2⋅|a|                (I)

而(I)现在只是(i)fork_2 = 1/2和n_0 = 2⋅|a|。

---

包起来

我们总结：

(I) & (II) => (1/2)⋅n ≤ n + a ≤ 2⋅n

With b>0, this yields: 

   ((1/2)⋅n)^b ≤ (n + a)^b ≤ (2⋅n)^b                (**)

(**)，我们证明了(*)成立，有

c_1 = k_1^b = (1/2)^b = 2^(-b)
c_2 = k_2^b = 2^b   (note that the solution you posted has an error here)
n_0 = 2⋅|a|

因此，我们已经证明了f(n)as in (+)，Θ(g(n))with g(n)as in (++)。

---

最后请注意，常数c_1, c_2( k_1, k_2) 和n_0in的选择(*)不是唯一的：存在无数种方法来证明(*)成立（如果成立），或者不存在。在这种情况下，您的解决方案的作者的特定选择很自然，但我们可以选择任意数量的其他常量集。