空间复杂性复发

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。