algorithm - クイックハル 最悪の場合の説明

Question

クイックハルの最悪のケースは?? そして、それが最悪のケースであることをどのように知ることができるのか、クイックハルアルゴリズムと混同しています。実際、三角形の面積を求めるための行列式を実行し、面積が正の場合、その点は極値の左側にあることを理解しました。そして、これを再帰的に行うと、船体を構築するための効率が O(n) になります。次に、効率化の方法が O(nlogn) および )(n^2) と言及されることがあることを理解していませんか? この効率はどのような場合に、どのように得られるのでしょうか? 誰かが特定の例で助けてくれるならお願いします; それは大きな助けになるでしょう。

Answer 1

受け入れられた答えが正しくないのではないかと心配しています。

実際、上記のケースはO(n log n)ケースです。再帰ツリーを見てください。各ステップで、点のセットをほぼ同じ大きさの 2 つのサブセットに分割します。したがって、再帰ツリーの高さはO(log n)であり、全体の実行時間はO(n log n)になります。

より正確に言うと、quickhull アルゴリズムの再帰関係はT(n) = T(a * n) + T(b * n) + c*nです。最後の項 ( c*n ) は、ピボット要素の検索を表します。上記の場合、定数aとbはa = b = 1/2です。マスター定理を使用して、O(n log n)の範囲を決定できます。

最悪の場合のO(n ² )は、a*n ≈ n-1およびb*n ≈ 1です。次の規則 (極座標) を使用して、円の境界に点を配置することにより、それを作成できます: P _i = (r, π / 2 ⁱ ) . このポイントのセットでは、ピボット要素は常に最も左のポイントになるため、セットは n-1 ポイントを含むサブセットと空のサブセットに分割されます。したがって、再帰の各ステップでは、1 つのポイント (ピボット要素) のみを「削除」します。したがって、再帰ツリーの高さはO(n)であり、全体的な効率はO(n ² )になります。

Answer 2

QuickHull は、ステップの 1 つで三角形の内側にある一連の点を削除するため、高速なアルゴリズムです。QuickHull の手順は次のとおりです。

1. 右端と左端の点を選択し、それらの間の線をたどります
2. あなたの線から最も遠い点を見つけます
3. これらの 3 点間に三角形を描きます
4. 三角形内の点を削除して、ステップ 2 に戻ります。

これは、ポイントが平面上にランダムに配置されている場合ですが、ポイントの分布が悪く、特定のステップでそれらのいずれも削除できない場合があります。このケースの 1 つは、点が円の境界にある場合です。

ご覧のとおり、これが発生した場合、上記のアルゴリズムのステップ 4 では、ポイントをまったく削除しません。これが、最悪の場合、QuickHull がO(n^2).