algorithm - 私のスクリプトの大きな O 表記の値が気になりますか?

Question

何かの大きなO表記を推定してから少し時間が経ちましたが、これを理解できないようです。基本的に、私のスクリプトは、緯度/経度で米国内のポイントのリストを実行し、それらのポイントが半径 100 マイルの円の中心である場合に、その国をカバーするセットを見つけます。このように：

score 1 · Accepted Answer

あなたのアルゴリズムはO(N^2)、ここでnです。あなたの説明を正しく理解すると、次のようになります。

for point A in array:
  for point B in array:
      d = dist(A,B)
      //optionally remove from list

最悪の場合、ポイントのすべてのペアが 100 マイル以上離れているため、最終的に各ペア間の距離をチェックすることになりO(N^2)ます。

n + (n-1) + (n-2) + ... + 2 + 1 = (n(n+1))/2ほとんどの距離計算を行っていることに注意してください。これはまだO(N^2)です。

score 1 · Accepted Answer

O(n^2)最悪の場合、配列を反復処理し、配列内の次のすべてのポイントに対して各ポイントをチェックするため、アルゴリズムのランタイムはです。したがって、n(n-1)/2比較は次のとおりです。O(n^2)

ただし、このアルゴリズムが問題に対する適切な解決策を提供するとは思わないことをお伝えしなければなりません。

score 0 · Accepted Answer

n入力として持っているポイントの数だとしましょう。

リストのループを開始します。インデックス i = 0 です。

...

i = リストの長さの場合、終了、そうでない場合、ループ

それがn反復です。

リスト内の i 番目の点と、リスト内のそれ以降のすべての点の間の距離を見つけます。

それnは反復ごとの操作です。これらの 2 つだけの場合は、最終的には次のようになりn^2/2ます (すべてのポイントと他のすべてのポイント。ただし、順序は重要ではないため、半分の比較を行います)。

100 マイル以内のポイントを削除します

配列の再インデックス

100 マイル以内にある要素を無効にしてから、配列をシフトしているように聞こえます。どちらもO(n)操作であり、操作が繰り返されるO(n^2)ためです。O(n)n

だからあなたは持ってしまいますO(n^2)。

3 に答える 3