构造一个复杂度为 O(n) 的平均情况算法，从 n 个点的列表中找到最接近的 m 个点
Construct an O(n) average case algorithm to find closest m points from a list of n points
我们需要构造一个算法，给定一个笛卡尔平面上的n个点的列表，最近的m个（m不是常量，小于等于n）指向原点。这个算法需要在 O(n) 的平均时间内工作，这是我一直在努力解决的问题。
我最初的想法是根据每个点与原点的距离对列表进行排序，select 排序列表中的前 $m$ 个点。然而，我所知道的所有排序算法的平均时间都是 O(nlogn)。有没有其他方法可以做到这一点，使用笛卡尔平面的属性？
感谢您的帮助。
使用QuickSelect算法找到第m个离原点最近的点。这会将列表划分为最近的 m 个点，然后是更远的点。
我们需要构造一个算法，给定一个笛卡尔平面上的n个点的列表，最近的m个（m不是常量，小于等于n）指向原点。这个算法需要在 O(n) 的平均时间内工作，这是我一直在努力解决的问题。
我最初的想法是根据每个点与原点的距离对列表进行排序，select 排序列表中的前 $m$ 个点。然而，我所知道的所有排序算法的平均时间都是 O(nlogn)。有没有其他方法可以做到这一点，使用笛卡尔平面的属性？
感谢您的帮助。
使用QuickSelect算法找到第m个离原点最近的点。这会将列表划分为最近的 m 个点，然后是更远的点。