递推码的空间复杂度

Question

考虑以下Java方法：

   public static void f(int n) {
    if (n<=1) { 
       System.out.print(n) ; 
       return; 
   }else {
       f(n/2) ;
       System.out.print(n);
       f(n/2);
    }
 } // end of method

问题3.设S(n)表示f(n)的空间复杂性。下列哪种说法是正确的？

• A: S(n) = (2n)
• B: S(n) = ( n)
• C: S(n) = (log N) <-正确答案，有人知道为什么吗？
• D:上述

F 210

Answer 1

每当函数递归地调用自己时，所有局部变量都留在堆栈上，并将新的一组局部变量推送到堆栈中进行新调用。这意味着您关心最多有多少次调用，换句话说，递归的最大深度是多少。

很明显，它是log n，因为连续的论证元是n，n/2，n/4，…，1。局部变量的数量是恒定的，即1(堆栈上需要空间)，因此总的空间复杂度是O(log )。