这个递归算法的顺序/递推公式/闭合公式是什么？

Question

我有一个算法称为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）），但我对我的解释犹豫不决。任何人都可以帮我吗？

Answer 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)的值时，您需要调用rec() n次，因此复杂度为O(n)。