私はなぜ最悪の場合はブルートフォースアルゴリズムの時間を実行している、問題は「ポイントの最も近いペア」（それに慣れていない場合thisを参照）についてブルートフォースポイントの最も近いペア。なぜO（n^2）ですか？
この質問をのための愚か感じるが、... O（n^2）？
n = 4とすると、いずれの方向からでも2つの点を比較することを検討すると、探索空間で比較できる点の対が12個しかありません。 2点を2回比較しないと、6になります。
O（n^2）は私に加算されません。ビッグO記法で
実際の比較回数はn*(n-1)/2です。これはn^2/2-n/2に等しい。しかし、big-O表記法では、あなたは支配的な言葉にしか関心がありません。 nという非常に大きな値では、n^2という用語の係数のように、-n/2という用語の重要性は低くなります。だから、我々はそれがO(n^2)だと言う。
Big-O表記は、撮影時間またはステップ数の正確な公式を示すものではありません。それは複雑さ/時間の順序を与えるだけなので、大きな入力に対してどのようにスケーリングするのかの感覚を得ることができます。
そして係数を気にしない理由は、一定の要素によって、より速くまたは遅いコンピュータをいつでも購入/構築できるということです。それとも、私たちはもっともっと患者になることができます。 :) – biziclop
大きなポイント。また、アルゴリズムの優れた実装と悪い実装の間で、2つの要素の差を簡単に取得できます。 –
、そのように、乗算定数を考慮することができる：
O(k*(n^2)) = O(n^2)
アイデアは定数（OP例で1/2、距離比較が反射性であるため）がないことです複雑さについて何か新しいことを教えてください。それは入力の2乗でまだ大きくなります。
アルゴリズムのブルートフォースバージョンでは、可能なすべての点のペアを比較します。 nポイントのそれぞれについて(n - 1)と比較すると、すべてのペアを1回取ると(n * (n - 1))/2の比較結果となります。 O(n^2)という悲観的な複雑さは、いくつかの定数がkの場合、操作の数がk * n^2に束縛されることを意味します。 Big O表記では、正確な操作数はわかりませんが、データサイズ（n）が大きくなると比例する関数になります。
ブルートフォースを適用すると、可能なすべてのペアをチェックすることが強制されます.Nポイントを考えると、各ポイントに対して、距離を計算する必要があるN-1個の他のポイントがあります。したがって、計算可能な距離の合計= N点* N-1個の他の点。しかし、処理の過程で我々は距離を2倍にしました。 AからBまでの距離は、AからB、またはBからAのいずれかが計算されるかどうかのままです。したがって、N *（N-1）/ 2。したがって、O（N^2）。
「n = 3」はどうですか？そして、「n = 5」についてはどうですか？ – arekolek
ステップ数はO（n^2）に比例しますが、それらは等しくなくてもかまいません。 – Lee