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

Question

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

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

我们想找到 ac 使得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 , 左边就少了 , 所以 if 2n+2 <= 4n, 肯定2n + 2 <= 4n + 4

因此，您基本上从2n+2 <= 4n（根据归纳假设您知道这是正确的）跳到2n+4 <= 4n+4，因为2<4和2n+2<=4n。您稍后会发现诱导假设的主张在n+1接下来的几行中也是正确的。