4

Aho、Hopcroft、Ullman の「データ構造とアルゴリズム」を読んでいて、演習 1.12 B と混同しています。

この Pascal 手続きの計算量 (Big O 表記で表される) はどれか?

procedure mysterious( n: integer );
    var
        i, j, k: integer;
    begin
        for i := 1 to n - 1 do
             for j := i + 1 to n do
                 for k := 1 to j do
                    {mysterious statement of O(1)}
    end

手伝っていただけませんか？

ありがとう！

4

1 に答える 1

6

O(n 3 )です。大きなOは、実行時間（またはメモリなど）がタスクのサイズにどのように比例するかを示しています（比例係数は省略されています）。

この場合、内部ステートメントは (n 3 ) に比例する回数実行されます。i は 1 から (n-1) まで実行されるため、外側のサイクル内のすべてが (n-1) 回実行されます。j は平均して (n/2) から (n) まで実行されるため、内部のすべてが (n-1)* (n/2) 回実行されます。k は平均して 1 から (3/4* n) まで実行されます。これは、内部ステートメントの (n-1)* (n/2)* (3/4*n-1) 回の実行を取得します。これは O(n 3 ) です。

于 2009-03-20T05:07:07.697 に答える