algorithm - Big O、アルゴリズム分析

Question

以下の各ステートメントの大きな O 表記は何なのか疑問に思っています。

Sum = 0;
 for i=1 to N^2 do:
   for j=1 to N do:
    'Sum += 1;

Sum = 0 は、一度しか実行されないため、確かに O(1) です。しかし、2 番目のステートメントに混乱しています。最初のループなので、O(N) にする必要がありますか? または、N ^ 2 は変数 N に関する二次関数であるため、O(N ^ 2) にする必要がありますか?

score 6 · Accepted Answer

^{最初のループは、N 2}ステップを実行するため、O(N ² )です。これらの各ステップは、N 個のステップを含む内側のループを実行するため、N ² * N または N ^{3 個}のステップがあり、アルゴリズムは O(N ³ ) です。

score 2 · Accepted Answer

2

N 3 ラウンドをループすることになるので、次のように言います: O(n^3)

于 2013-09-08T00:24:18.007 に答える

score 0 · Accepted Answer

アルゴリズム：

Sum = 0; ~ 1

 for i=1 to N^2 do: ~ 1+2N^2
   for j=1 to N do: ~ (1+2N) * N^2
    'Sum += 1; ~ 1 * N * N^2

時間の複雑さ:

Time = 1 + 1+2N^2 + (1+2N)*N^2 + 1 * N * N^2

Time = 2 + 2N^2 + N^2 + 2N^3 + N^3

Time = 2 + 3N^2 + 3N^3

O(Time) = O(2 + 3N^2 + 3N^3) ~ O(N^3)

3 に答える 3