3

"n 個の整数の配列が与えられた場合、それらの階乗の配列を返します。"

配列を反復処理してそれぞれの階乗を見つける単純な方法の代わりに、以前に計算された階乗を保存し、それらを後続の階乗で使用する、メモ化されたアプローチを考えていました。

例: 7! 結果6ならかなり速く計算できる！どこかに保管されています。ただし、両方のアルゴリズムの実行時間はまだ O(n) であることに気付きました。(私は間違っているかもしれません) それは、ここでプロセスをスピードアップしていないことを意味しますか? もしそうなら、メモ化は非ツリー再帰の問題では役に立たないということですか? (フィボナッチでは、以前に見つかった値をメモすることで再帰ツリーを効果的に刈り込みます。階乗の場合、再帰のはしごのように、実際にはツリーを持っていません) コメントを歓迎します。

4

2 に答える 2

1

メモ化なしの場合、メモ化なしで factorial(i) を計算するには (i-1) 回の乗算が必要になるため、時間計算量は O(n^2) になります。

于 2013-02-09T13:50:41.900 に答える
1

ただし、両方のアルゴリズムの実行時間はまだ O(n) であることに気付きました。

O-Notation はここに最も重要な特徴を隠しています。階乗を扱うときにはるかに重要な数値のサイズではなく、配列の長さのみを考慮します。

ハッシュテーブルを使用してメモ化を実装する必要があります。そうすると、漸近的に各エントリに対して O(1) が得られます。

于 2013-02-09T11:31:17.453 に答える