是不是遞歸線性的斐波那契算法？

Question

我知道斐波那契算法可以在不遞歸這樣的編程：

int fibo(int n){ 
if(n <= 1){ 
    return n; 
} 
int fibo = 1; 
int fiboPrev = 1; 
for(int i = 2; i < n; ++i){ 
    int temp = fibo; 
    fibo += fiboPrev; 
    fiboPrev = temp; 
} 
return fibo; 
} 

，也該遞歸斐波那契具有複雜度O（2^k）的約，但我所看到的非遞歸算法是O（n）;所以它看起來更有效率，是不是我的微積分還是非遞歸解決方案中存在任何隱藏的複雜性？

Answer 1

獨立評估實現的複雜性。在這種情況下，與輸入n相關的複雜度由for循環定義，它與n的大小成正比。因此，複雜度是O（n） - 線性的。