1

次の 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: 上記のいずれでもない
4

1 に答える 1

6

関数が自分自身を再帰的に呼び出すときは常に、すべてのローカル変数がスタックに残り、それらの新しいセットが新しい呼び出しのためにスタックにプッシュされます。これは、最大でいくつの呼び出しがあるか、つまり、再帰の最大深さがどのくらいかを気にすることを意味します。

連続する引数が n、n/2、n/4、...、1 であるため、log n であることは明らかです。ローカル変数の数は一定であり、つまり 1 (スタック上にスペースが必要です) です。全体的なスペースの複雑さは O(log n) です。

于 2012-06-19T06:19:34.063 に答える