空间复杂度递归

Question

所以这是一个两部分的问题。

我有一些要求时间复杂度的代码，它由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) (依此类推)，所以您只需要同时使用的最大空间，即<代码>d21。