複雜性的函數的

是什麼的時間和空間複雜度：複雜性的函數的

int superFactorial4(int n, int m) 
{ 
    if(n <= 1) 
    { 
     if(m <= 1) 
      return 1; 
     else 
      n = m -= 1; 
    } 

    return n*superFactorial4(n-1, m); 
}

它通過減1，n的值，直到它等於1遞歸地運行，並且然後它要麼減1的m的值或者當m返回1等於1

我認爲複雜性取決於兩個n和m，所以也許這是O（N * M）。

來源

2009-02-10 yyy

我的頭快要爆炸了。 – 2009-02-10 11:37:35

這看起來像一個家庭作業給我。 – 2012-11-14 00:08:23

時間複雜度爲O(n+m^2)，空間複雜度相同。

推理：用m固定值，該功能使得n遞歸調用本身，每一個做持續的工作，所以固定電話m的複雜性是n。現在，當n達到零時，它變成m-1並且m也變成m-1。所以下一個固定的m相將取m-1，接下來的m-2等等。所以你得到一筆(m-1)+(m-2)+...+1這是O(m^2)。

的空間複雜度是相等的，因爲每個遞歸調用，遞歸需要不斷的空間，你永遠不會從遞歸返回除了在結尾，而且沒有尾遞歸。

來源

2009-02-10 11:32:49 jpalecek

實際上，它看起來是更接近O（N + M^2）給我。 n僅用於第一個「循環」。

而且，在沒有做尾調用優化的空間複雜度可能是任何語言「失敗」。在支持優化的語言中，空間複雜度更像O（1）。

來源

2009-02-10 11:33:27 Darron

-1

使用遞歸僞代碼階乘函數的時間複雜度：

int fact(n) 
{ 
    if(n==0) 
    { 
     return 1; 
    } 
    else if(n==1) 
    { 
     return 1; 
    } 
    else if 
    { 
     return n*f(n-1); 
    } 
} 

time complexity;  
let T(n) be the number of steps taken to compute fact(n). 


we know in each step F(n)= n*F(n-1)+C 

F(n-1)= (n-1)*F(n-2)+c 

substitute this in F(n), we get 

F(n)= n*(n-1)*F(n-2)+(n+1)c

現在用大O符號，我們可以說，

F(n)>= n*F(n-1) 
F(n)>= n*(n-1)*F(n-2) 
. 
. 
. 
. 
. 
F(n)>=n!F(n-k) 

T(n)>=n!T(n-k) 

n-k=1; 
k=n-1; 

T(n)>=n!T(n-(n-1)) 
T(n)>=n!T(1) 
since T(1)=1 
T(n)>=1*n!

現在是在

形式

F(n)>=c(g(n))

所以我們可以說使用遞歸的因子時間複雜度是

T(n)= O(n!)

來源

2011-09-23 14:42:06 kamal

複雜性的函數的

回答

相關問題