2

時間計算量が O(4^n) のメソッドを書くようにという質問を受けました。

私はこのアルゴリズムを思いついた：

public void test(int n){
   for(int i = 0; i<n;i++){
      test(4*i);
   }
}

これは O(4^n) で実行されていると見なされますか?

4

4 に答える 4

3

あなたはあなたのプログラムに非常に近かった。正しい関数は次のようになります。

public void test(int n) {
  if (n == 0) return;
  for (int i = 0; i < 4; i++) test(n-1);
}

次のコードを実行して確認します。

static int runs;
static void test(int n) {
  runs++;
  if (n == 0) return;
  for (int i = 0; i < 4; i++) test(n-1);
}
public static void main(String[] args) {
  for (int n = 1; n <= 5; n++) {
    runs = 0;
    test(n);
    System.out.format("%d: %d %d\n", n, 1<<(2*n), runs);
  }
}

印刷します

1: 4 5
2: 16 21
3: 64 85
4: 256 341
5: 1024 1365

実行回数は 1 つずれていますが、big-O の複雑さは満たされています。

なぜ O(4 n )であるかについての理由は、一度見ればおそらく非常に明白ですが、少し説明しても害はありません。この機能は、分割統治によって複雑な問題を解決していると最もよく想像されます。nサイズの問題を ( n-1 ) サイズの問題の 4 つのインスタンスに縮小し、サブ問題が自明 (サイズ 0) になるまで繰り返します。したがって、サイズ 1 の問題は 1+4 ステップ (エントリポイント呼び出し + 4 つの自明な部分問題) で解決されます。サイズ 2 in 1 + 4*(1 + 4) = 21 ステップの問題など。

于 2012-10-14T12:35:10.260 に答える
3

いいえ、そうではありません。

test(0) を呼び出すと、すぐに戻ります。負の数で test を呼び出すことも同様です。

正の数で test を呼び出すと、返されることはありません (オーバーフローで返されますが、これは通常、複雑さを計算するときに考慮されません)。

于 2012-10-14T12:01:51.400 に答える
1

言われているように、それは 1 より大きい与えられた入力に対して永久に実行されます。4^n の複雑さのプログラムを書くには、n-1 よりも n の方が 4 倍複雑になる操作について考えてみてください。たとえば、n = 1 の場合は正方形を 4 つの小さな正方形に分割し、n = 2 の場合はそれらの正方形を再度分割します...

四角形の数が 4^n になることがわかり、アルゴリズムの時間の複雑さも同様です。

ただし、大きな o 表記は上限を表すため、O(n) である操作も O(4^n) になることを理解してください。ただし、それは意図したものではないと思います...

于 2012-10-14T12:16:05.990 に答える
1

いいえそうではありません。このプログラムは、1 より大きい数に対して無限に実行されます。したがって、O(4^n) ではありません。

于 2012-10-14T12:05:07.113 に答える