B樹修訂

Question

如果我們正在尋找線的交點（水平和垂直線只），我們有一半的垂直n行並沒有交集，然後

分揀線終點的y值之列表會採取使用歸併

每個插入刪除和查找我們的數據藥結構的（假設它的一個b-tree）將<爲log N

因此總的搜索時間將是N日誌N

N日誌ñ如果我在這裏錯過了什麼他使用mergesort進行排序的時間需要N log N的時間，插入和刪除需要一段時間< log n我們是否將常數因子降低到N log N的整個時間。如果不是那麼怎麼回事< log n缺失在總的運行時間？

謝謝

Answer 1

big-O符號描述算法的漸近行爲。也就是說，它將算法的行爲描述爲朝向無窮大的趨勢。算法的這一部分需要花費時間的部分算法，該部分需要日誌N時間。 N部分的重要性減小到相對無關，因爲N變大。

Answer 2

我懷疑你的導師指的是Line Segment Intersection的問題，這比簡單的排序片段更復雜。您會注意到，本文引用了Shamos-Hoey算法，該算法使用二叉樹來存儲線段並有效檢測交點。

邁克爾是正確的，因爲使用二叉樹對於一次性排序的線段沒有意義。但是，在檢測交叉點的情況下，排序後跟搜索將產生二次性能，並不是最好的方法，因此線檢測算法使用二叉樹。

例如，假設您按照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樹結構。