我有一个叫做 rec(n) 的算法:
rec(n)
if (n=0) return 1
else
i=rec(n-1)
A[n]=i
return i
我在看它，据我所知，无论你在其中放什么，它总是返回 0 值，所以我假设递归关系是 a(n)=a (n-1) 并且时间复杂度将是恒定的(即 O(1))，但我对我对它的解释犹豫不决。谁能帮帮我？
最佳答案
你是对的，无论 n 的值是多少，rec(n) 都将始终返回 1。这可以通过使用关系 rec(n) = 的归纳法简单地证明rec(n-1) 与基本情况 rec(0) = 1。
另一方面，您的函数rec(n) 的复杂度应该是O(n)。这是因为当你计算rec(n)的值时，你首先需要计算rec(n-1)的值；但是为了找到 rec(n-1) 你需要计算 rec(n-2) 的值等等。
因此在计算rec(n)的值时，需要调用n次rec()，复杂度为O(n).
关于algorithm - 这个递归算法的阶数/递归公式/闭合公式是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26748664/