這個遞歸算法的順序/遞推公式/閉合公式是什麼？

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)。