performance - 证明时间复杂度函数的效率等级

Question

以下是解决方案，但我无法通过归纳部分理解证明的 1 部分。为什么可以只在一侧添加 +2 而在另一侧添加 +4？

我们正在处理函数 T(n) = 2n + 2

我们想找到一个 c 使得 T(n) <= c * f(n)对于大的n

我们有T(n) = 2n + 2和 f(n) = n , 所以我们需要 2n + 2 <= c * n

我们求解 c 并得到 2 + 2/n

2/n在 n = 0 时未定义，所以我们选择 t >= 1 .我们会选择t=1 , 所以 c=4

归纳法证明:

         T(n) <= c * f(n)
     (2n + 2) <= (4)(n)
          +2     +4              <---- Don't understand
      2n + 4  <= 4n + 4
2(n + 1) + 2  <= 4(n + 1)
     T(n + 1) <= c * f(n + 1)

结论:2n + 2 ∈ O(n)

Answer 1

如果2n+2 <= 4n ，通过向左手边加 2 和向右手边加 4，左手边加的少，所以如果 2n+2 <= 4n , 绝对 2n + 2 <= 4n + 4

所以，你基本上是从2n+2 <= 4n跳出来的(你知道归纳假设是正确的)到 2n+4 <= 4n+4 , 自 2<4和 2n+2<=4n .你后来发现归纳假设的主张对于 n+1 也是正确的。在接下来的几行中。