为什么代入法在确定递归函数的时间复杂度时需要证明精确形式
Why the substitution method need to prove the exact form when determining time complexity of recursive functions
用代入法求递归函数的时间复杂度时，为什么要证明精确形式而不能' t 使用定义的 渐近符号 。 “算法简介”一书第 86 页的示例：
T(n) ≤ 2(c⌊n/2⌋) + n
≤ cn + n
= O(n) wrong!!
为什么会这样？
根据 Big-O 的定义：O(g(n)) = {f(n)：存在正常数 c2 和 n0 使得 0 ≤ f(n) ≤ c2g( n) 对于所有 n > n0}，解决方案似乎是正确的。
假设 f(n) = cn + n = n(c + 1)，g(n) = n。那么n(c+1)≤c2nifc2≥c+1。 => f(n) = O(n).
是不是因为 f(n) 实际上是 T(n) 而不是 cn + n，而是 g(n) = cn + n？
如果能提供有用的答案，我将不胜感激。
在此 paper 的第 2 页描述了问题。这个解决方案之所以错误，是因为在每一层递归中，cn+n 中多出来的 n 都加起来了。正如论文所说“在许多递归调用中，那些“加号”加起来”
编辑（可能有更多时间回答）。
我在问题中试图做的是通过归纳法解决问题。这意味着我表明下一个递归对于我的时间复杂度仍然是正确的，这意味着它适用于之后的下一个递归，依此类推。然而，只有当我计算的时间复杂度低于我的猜测（在本例中为 cn）时，这才是正确的。例如 cn + n 大于 cn，因此我的证明失败了。这是因为，如果我现在让递归再进行一次，我将从 cn + n 开始。这将被计算为 c(cn + n) + n = n * c^2 + cn + n。这会随着递归级别的增加而增加，并且不会随着 O(n) 的增加而增加。因此它失败了。然而，如果我的证明被计算为 cn 或更低（想象一下），那么下一个级别将是 cn 或更低，就像下面的级别等等。这导致 O(n)。总之计算需要低于或等于任务
用代入法求递归函数的时间复杂度时，为什么要证明精确形式而不能' t 使用定义的 渐近符号 。 “算法简介”一书第 86 页的示例：
T(n) ≤ 2(c⌊n/2⌋) + n
≤ cn + n
= O(n) wrong!!
为什么会这样？
根据 Big-O 的定义：O(g(n)) = {f(n)：存在正常数 c2 和 n0 使得 0 ≤ f(n) ≤ c2g( n) 对于所有 n > n0}，解决方案似乎是正确的。
假设 f(n) = cn + n = n(c + 1)，g(n) = n。那么n(c+1)≤c2nifc2≥c+1。 => f(n) = O(n).
是不是因为 f(n) 实际上是 T(n) 而不是 cn + n，而是 g(n) = cn + n？
如果能提供有用的答案，我将不胜感激。
在此 paper 的第 2 页描述了问题。这个解决方案之所以错误，是因为在每一层递归中，cn+n 中多出来的 n 都加起来了。正如论文所说“在许多递归调用中，那些“加号”加起来”
编辑（可能有更多时间回答）。
我在问题中试图做的是通过归纳法解决问题。这意味着我表明下一个递归对于我的时间复杂度仍然是正确的，这意味着它适用于之后的下一个递归，依此类推。然而，只有当我计算的时间复杂度低于我的猜测（在本例中为 cn）时，这才是正确的。例如 cn + n 大于 cn，因此我的证明失败了。这是因为，如果我现在让递归再进行一次，我将从 cn + n 开始。这将被计算为 c(cn + n) + n = n * c^2 + cn + n。这会随着递归级别的增加而增加，并且不会随着 O(n) 的增加而增加。因此它失败了。然而，如果我的证明被计算为 cn 或更低（想象一下），那么下一个级别将是 cn 或更低，就像下面的级别等等。这导致 O(n)。总之计算需要低于或等于任务