3

実行時間に関する課題で問題があります。

問題文は次のとおりです。「イザベルは、整数 n の配列 A の値を合計する興味深い方法を持っています。ここで、n は 2 のべき乗です。彼女は A の半分のサイズの配列 B を作成し、B[i] を設定します。 = A[2i] + A[2i+1], for i=0,1,…,(n/2)-1. B のサイズが 1 の場合、彼女は B[0] を出力します. そうでない場合、彼女は A をB, そしてプロセスを繰り返します. 彼女のアルゴリズムの実行時間は?」

これは O(log n) または O(n) と見なされますか? 最終結果が得られるまで配列を半分に分割し続けるため、O(log n) を考えています。O(log n) の基本は、データ構造全体を走査しないことです。ただし、合計を計算するには、配列内の各要素にアクセスする必要があるため、O(n) である可能性があると思います。これを理解するための助けをいただければ幸いです。

4

2 に答える 2

2

自分で考え出したように、合計を計算するにはすべての要素にアクセスする必要があります。だからあなたの提案：

O(log n) の基本は、データ構造全体を走査しないことだと思います

保持しません。アルゴリズムがその時点である可能性は無視しても問題ありませんO(log n)。

あるO(n)とか違うとか、全体でどれくらいの操作をするかを考える必要があります。ジョージ・スコプツォフの答えは、それについて良いヒントを与えてくれます。（私自身の経験から）「実行時間」を決定するには、メモリアクセス、操作、入力と出力など、すべてを考慮する必要があるという事実に注意を喚起したいと思います。単純なケースでは、アクセス数 (または合計数) を見るだけで十分かもしれませんが、実際には、問題をあらゆる角度から見ないと、非常に歪んだ結果になる可能性があります。

于 2013-02-25T23:38:18.973 に答える
2

O(log n) の基本は、データ構造全体を走査しないことだと思います。

信念や推測に根拠はありません。アルゴリズムを精神的に実行します。Asizeの配列に対して何回の再帰があるnでしょうか? (配列 A のサイズが の場合) 再帰ごとに何回の合計がありnますか?

  • 最初の実行:n/2合計、n要素へのアクセスA
  • .
  • .
  • .
  • 最後の実行:1合計、2要素へのアクセスA

合計何回実行されますか? これを合計すると、 の最大のパワーはn何ですか?

于 2013-02-25T23:39:52.993 に答える