如何提高排序列表上每個列表的功能的複雜性？

下面的函數：如何提高排序列表上每個列表的功能的複雜性？

sortByDist :: (Ord a, Floating a, RealFrac a) => [V2 a] -> Map (V2 a) [V2 a] 
sortByDist graph = Map.fromList $ map sort graph where 
    sort point = (point, sortBy (comparing (distance point)) graph)

地圖中的列表上的每個點P到通過其P.距離有序點的列表因此，舉例來說，sortByDist [a, b, c, d] Map.! b是列表並[b，A，C，d]如果a是b的最近點，c是第二近的，d是第3個。

由於它對每個元素執行n * log n排序，因此複雜度爲n^2 * log n。這符合進行排序的N個點的列表所需要的時間基準：

points time 
200  0m0.086s 
400  0m0.389s 
600  0m0.980s 
800  0m1.838s 
1000 0m2.994s 
1200 0m4.350s 
1400 0m6.477s 
1600 0m8.726s 
3200 0m39.216s

多少可以這樣理論上改進？是否有可能將其降至N * log N？

來源

2015-03-02 MaiaVictor

看起來像一個四叉樹的一些變種可能會在這裏有所幫助。 – luqui 2015-03-02 08:18:04

對於我來說，看起來「顯而易見」的是，你無法以該輸出格式低於'N^2' - 這是它的大小，並且不太可能具有可靠的共享。我不知道如何做到這一點。 – 2015-03-02 08:21:31

你確定它不可能有可靠的共享？由於輸出的每個元素都是同一個圖的排序表示，我猜想他們之間有大量的重複信息。 – MaiaVictor 2015-03-02 09:14:04

由於luqui commented，使用四叉樹或類似可能會有所幫助。構建樹應該採用O（n log n）：log n pass，每個都是O（n）選擇和分區。一旦你有樹，你可以遍歷它來建立列表。節點與其子節點的列表之間的差別通常應該很小，而當節點與其子節點之間的差異很大時，這往往會迫使其他節點變小。因此，使用自適應排序（例如自適應合併排序或自適應排序排序）應該具有良好的性能，但分析複雜性並不容易。如果你想嘗試獲得一些共享，你將不得不使用序列類型來表示這些列表（例如Data.Sequence），然後嘗試找出各種尺度下的正方形之間的關係。我對這種方法降低時間複雜性的可能性深表懷疑。

來源

2015-03-02 15:58:03 dfeuer

如何提高排序列表上每個列表的功能的複雜性？

回答

相關問題