如何提高函数的复杂性,为其上的每个点对列表进行排序？

Question

以下功能:

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是第三个.

由于它对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？

Answer 1

正如luqui 评论的那样，使用四叉树或类似的东西可能会有所帮助。构建树应该花费 O(n log n)：log n 遍，每次选择和分区都是 O(n) 次。获得树后，您可以遍历它来构建列表。节点及其子节点的列表之间的差异通常应该很小，并且当其中一些列表很大时，这往往会迫使其他列表变小。因此，使用自适应排序（例如，自适应合并排序或自适应展开排序）应该能够提供良好的性能，但分析复杂性并不容易。如果您想尝试获得一些共享，则必须使用序列类型（例如Data.Sequence）来表示列表，然后尝试找出不同比例的方块之间的关系。我对这种方法降低时间复杂度的潜力表示严重怀疑。