递归码的空间复杂性

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)的空间复杂度.以下哪项陈述是正确的？

• 答:S(n)=(2n)
• B:S(n)=(n)
• C:S(n)=(log n)< - 正确答案,有谁知道为什么？
• D:以上都不是

Answer 1

每当函数以递归方式调用自身时,所有局部变量都保留在堆栈中,并将一组新的局部变量推送到堆栈以进行新调用.这意味着您关心最多有多少个调用,换句话说,递归的最大深度是多少.

很明显它是log n,因为连续的参数是n,n/2,n/4,...,1.有一个恒定数量的局部变量,即1(堆栈上需要空间)因此整体空间复杂度为O(log n).