0

以下は私が書いた疑似コードで、配列 A と整数値 k を指定すると、A に合計が k になる 2 つの異なる整数がある場合は true を返し、それ以外の場合は false を返します。このアルゴリズムの時間の複雑さを判断しようとしています。

最悪の場合のこのアルゴリズムの複雑さは O(n^2) であると推測しています。これは、最初の for ループが n 回実行され、このループ内の for ループも n 回実行されるためです。if ステートメントは 1 つの比較を行い、true の場合は値を返します。これはどちらも一定時間の操作です。最後の return ステートメントも一定時間の操作です。

私の推測は正しいですか？私はアルゴリズムと複雑さに慣れていないので、どこかで間違っていたら訂正してください!

Algorithm ArraySum(A, n, k)
for (i=0, i<n, i++)
    for (j=i+1, j<n, j++)
        if (A[i]+A[j]=k)
            return true
return false
4

3 に答える 3

5

Azodious の推論は正しくありません。内側のループは単にn-1時間を実行するだけではありません。(outer iterations)*(inner iterations)したがって、複雑さの計算には使用しないでください。

注目すべき重要なことは、内側のループのランタイムが外側のループの反復ごとに変化することです。

n-1ループが最初に実行されるときに反復が行われるのは正しいことです。しかし、その後、反復の量は常に 1 ずつ減少します。

  • n - 1
  • n - 2
  • n - 3
  • …
  • 2
  • 1

ガウスのトリック (2 番目の式)を使用して、この級数を合計して を得ることができn(n-1)/2 = (n² - n)/2ます。これは、最悪の場合に合計で比較が実行される回数です。

このことから、境界が よりもきつくなることはできないことがわかりますO(n²)。ご覧のとおり、推測する必要はありません。

アルゴリズムは任意のステップの後に完了する可能性があるため、意味のある下限を指定できないことに注意してください。これは、アルゴリズムの最良のケースが であることを意味しますO(1)。

于 2012-09-25T08:36:22.443 に答える
1

はい。最悪の場合、アルゴリズムは O(n 2 ) です。

入力のすべてのインスタンスには時間計算量 O(n 2 ) が必要なため、アルゴリズムは O(n 2 ) です。 あなたのアルゴリズムは Ω(1) です。これは、入力のインスタンスが 1 つだけ存在し、時間の複雑さ Ω(1) しか必要としないためです。

以下は、 Cormen、Leiserson、Rivest、およびSteinが共著したアルゴリズム入門の第 3 章「関数の成長」に記載されています。アルゴリズムの実行時間 (修飾子なし) が Ω(g(n)) であると言うとき、n の各値に対してサイズ n の特定の入力が選択されても、その入力の実行時間はn が十分に大きい場合、少なくとも一定時間 g(n)。

最初の 2 つの要素の合計が k に等しい入力が与えられた場合、このアルゴリズムは true を返す前に 1 回の加算と 1 回の比較しか行いません。したがって、この入力には一定の時間の複雑さがかかり、このアルゴリズムの実行時間は Ω(1) になります。

入力が何であれ、このアルゴリズムは値を返す前に最大で n(n-1)/2 回の加算と n(n-1)/2 回の比較を行います。したがって、このアルゴリズムの実行時間は O(n 2 )です。

結論として、このアルゴリズムの実行時間は Ω(1) と O(n 2 )の間にあると言えます。このアルゴリズムの最悪の場合の実行は Θ(n 2 )であるとも言えます。

于 2012-09-25T08:27:24.817 に答える
-2

あなたは正しいですが、少し説明させてください。

これは、最初のforループがn回実行され、このループ内のforループもn回実行されるためです。

実際には、2番目のループは(n-i-1)何度も実行されますが、複雑さの観点からは、それだけと見なされますn。（phant0mのコメントに基づいて更新）

したがって、最悪の場合のシーンリオでは、それはn * (n-i-1) * 1 * 1何回も実行されます。これはO(n^2)です。

最良の場合、scenerioは、一定1 * 1 * 1 * 1時間実行されます。O(1)

于 2012-09-25T05:47:18.800 に答える