0

線の交点 (水平線と垂直線のみ) を探していて、半分が垂直で交点がない n 本の線がある場合、

y 値で線の終点のリストを並べ替えるには、mergesort を使用して N log N が必要です

データ構造の各挿入削除と検索 (B ツリーであると仮定) は < log n になります

したがって、合計検索時間は N log N になります

ここで欠けているのは、マージソートを使用してソートする時間が N log N かかり、挿入と削除に < log n の時間がかかる場合、N log N の全体時間を与えるために定数係数を削除することです。そうでない場合は、 ONotation の合計実行時間で < log n が失われるのはなぜですか?

ありがとう

4

2 に答える 2

1

big-O 表記は、アルゴリズムの漸近的な動作を表します。つまり、Nが無限大に向かうときのアルゴリズムの動作を記述します。N log N時間かかるアルゴリズムの部分は、log N時間かかるアルゴリズムの部分を矮小化します。log N部分の重要性は、 Nが大きくなるにつれて減少し、相対的にゼロになります。

于 2010-04-20T09:05:10.557 に答える
0

あなたの家庭教師は、単純にセグメントをソートするよりも複雑なLine Segment Intersectionの問題について言及していると思われます。この記事では、二分木を使用して線分を格納し、交点を効率的に検出する Shamos-Hoey アルゴリズムを参照していることに注意してください。

二分木を使用することは、線分の 1 回限りの並べ替えには無意味であるという点で、Michael は正しいです。ただし、交差を検出するコンテキストでは、並べ替えに続いて検索を行うと 2 次のパフォーマンスが得られ、最適なアプローチではないため、ライン検出アルゴリズムでバイナリ ツリーが使用されるのはこのためです。

たとえば、ライン セグメントを x 軸に沿って左から右に並べ替えるとします。単純な検出アルゴリズムは次のようになります。

for (int i=0; i<segs.length - 1; ++i) {
  boolean searching = true;

  for (int j=i+1; j<segs.length && searching; ++j) {
     if (segments overlap on x-axis) {
       // Check for intersection.
     } else {
       // No overlap so terminate inner loop early.
       // This is the advantage of having a sorted list.
       searching = false;
     }
  }
}

二重にネストされたループのため、最悪のケースは O(n^2) であり、すべての線分が x 軸上で重なっている場合に発生します。最良のケースは線形であり、x 軸上で重なり合うセグメントがない場合に発生します。

単純なアルゴリズムを実装することから始めてから、B ツリー構造を使用するアルゴリズムを実装することをお勧めします。

于 2010-04-20T10:39:52.220 に答える