一个永无止境的递归函数怎么会有时间复杂度？

Question

在 CLRS 的“Introduction to Algorithms”一书中，我们被要求求一个递归函数的时间复杂度：

4.4-8
Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(n - a) + T(a) + cn where a ≥ 1 and c > 0 are constants.

但是，当T(a)被调用时，T(a)又会被调用，T(a)又会再次调用T(a)，以此类推。这个分支永远不会有一个基本案例。因此，该函数将 永无止境！ 当该函数实际上会导致 O(∞) 时，该函数的时间复杂度怎么可能为 O(n^2)？

         n 
        / \
       /   \
   n - a     a
   / \      / \
  /   \    /   \
n-2a   a  0     a  <-- Never ending
/ \    /\      / \
      0  a     0  a
                   \  <-- No base case

O(n^2) 的证明Link, Link, Link:
这是数学证明与现实不符的情况，还是我误解了函数的实际含义？澄清一下，我没有询问数学证明是如何工作的，我只是不明白它怎么可能是我所描述的逻辑的正确答案。此外，O(n^2) 对这个函数意味着什么，只要 a > 0，每个 n 都会导致一个永无止境的函数，根据问题总是如此？

Answer 1

当为了确定复杂性而给出递推关系时，通常会忽略基本情况。

假设程序终止，那么如果x是任何常数，T(x)也是常数。您可以将它替换为常量，如“d”，或者记住您不必扩展它。

因为常数是什么并不重要，所以它通常被写成 O(1)，尽管这在形式上是不正确的，因为 O(1) 是一个集合。它也不适合您，因为您正在寻找紧绑定。

一个永无止境的递归函数怎么会有时间复杂度？

How can a never-ending recursive function have a time complexity?

algorithm

math

recursion

computer-science

clrs