空間複雜性復發

Question

所以這是一個2部分問題。

我有一些代碼，詢問的時間複雜度，它由3 for循環（嵌套）：

public void use_space(int n) 

    for(int i=0;i<N;i++) 
    for(int j=0;j<N;j++) 
    for(int k=0;k<N;k++) 

//and at the end of the code, it makes a recursive call to the function 
use_space(n/2); 
use_space(n/2); 

因此，我得出了這個時間複雜度複發率：T(n) = 2T(n/2) + n^3。我得到這個的原因是因爲有2個遞歸調用每個都由n/2個時間組成，並且嵌套for循環需要n^3次（3個循環）。

這是正確的嗎？

然後對空間的複雜性，我S(n) = S(n/2) + n

希望有人能澄清，並告訴我，如果這是錯誤/解釋。所有的幫助將不勝感激。

Answer 1

您的時間複雜性是正確的。您可以使用masters theorem將其簡化爲Theta(n^3)

但是您的空間複雜性似乎有點不正確。
對於每次撥打use_space(n)，您必須保存三個號碼i,j和k。這個數字最多隻有n（如果n == N，我想你把它們混合起來），所以它們需要保存log n位。由於在完成use_space後釋放空間，您只需保存一個附加電話use_space(n/2)。

所以你得到的空間複雜度爲S(n) = S(n/2) + 3 log n。

改進：你可以結束了三個環路後釋放i，j和k，所以你不需要3 log n和S(n/2)（同時），但首先3 log n這S(n/2)後，這將是弗里斯特3 log (n/2)然後S(n/4)（依此類推），所以你只需要同時使用的最大空間，即3 log n。