渐近分析不等式

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_1 和 k_2（与 c_1 和 c_2 相关，分别为 k_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| 都成立。好吧，让我们选择将我们的 n0 固定在 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) 对于 k_2 = 1/2 和 n_0 = 2⋅|a| 现在只是 (i)。

总结

我们总结：

(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) 在 Θ(g(n)) 中，而 g(n) 中的 (++).

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

渐近分析不等式

Asymptotic Analysis Inequalities

big-o

asymptotic-complexity

inequalities

准备工作

解决方案（详尽解释）