0 
for i = 0 to size(arr)
   for o = i + 1 to size(arr)
      do stuff here

これの最悪の複雑さは何ですか? 2番目のものはiループごとに1ずつ減少するため、N ^ 2ではありません。Nじゃないよ、もっと大きいはず。N-1 + N-2 + N-3 + ... + N-N+1.

4

4 に答える 4

9

です。これは N ^ 2、2 つの線形複雑度の積だからです。

(漸近的な複雑さが漸近的で同一ではないという理由があります...)

行われた単純化に関するウィキペディアの説明を参照してください。

于 2013-01-13T17:05:55.437 に答える
2

anxn行列を使用しているように考えてください。マトリックス内の要素のほぼ半分で作業していますが、O（n ^ 2/2）はO（n ^ 2）と同じです。

于 2013-01-13T17:09:39.873 に答える
1

にn*(n-1)/2等しいO(n^2)です。

于 2013-01-13T17:10:26.843 に答える
1

アルゴリズムの複雑度クラスを決定したい場合、アルゴリズムの複雑度関数で最も急速に増加する項を見つけるだけで済みます。たとえば、複雑な関数 がある場合f(n)=n^2-10000*n+400、 を見つけるO(f(n))には、関数内の「最も強い」項を見つけるだけです。なんで？十分に大きいためn、その用語だけが関数全体の動作を決定します。f1(n)=n^2-n-4そうは言っても、との両方f2(n)=n^2がにあることは簡単にわかりO(n^2)ます。ただし、同じ入力サイズのn場合、同じ時間実行されません。

あなたのアルゴリズムでは、 の場合n=size(arr)、do stuff hereコードは時間を実行f(n)=n+(n-1)+(n-2)+...+2+1します。f(n)が算術級数の和を表していることは簡単にわかります。f(n)=n*(n+1)/2つまり、 を意味しf(n)=0.5*n^2+0.5*nます。であると仮定するdo stuff hereとO(1)、アルゴリズムはO(n^2)複雑になります。

for i = 0 to size(arr)

が等しくなく、iより大きくなるとループが終了すると仮定しました。size(arr)ただし、後者の場合は、 よりもf(n)=0.5*n^2-0.5*n、まだ にありO(n^2)ます。O(1),O(n),0(n^2),... は複雑度クラスであり、アルゴリズムの複雑度関数は、入力サイズ n に対して、アルゴリズムにいくつのステップがあるかを表す関数であることを思い出してください。

于 2013-01-14T18:40:23.370 に答える