改进型桶排序实现K近邻位置查找的时间复杂度咨询

Let’s walk through the time complexity of this bucket sort-based approach step by step, since it has specific tie-breaking rules we need to account for.

Breakdown of Each Step #

1. Calculate distances and assign points to buckets

   • For each of the N points, we compute its squared distance to the origin (using x² + y² avoids floating-point operations and works perfectly for sorting purposes). This is an O(N) operation—each point takes constant time to process.
   • Assigning each point to a bucket (keyed by the squared distance) is O(N) on average if we use a hash map (like Java’s HashMap<Integer, List<Location>>), since each insertion is an average O(1) operation.

2. Sort each bucket

   • Since we need to prioritize points with smaller x-coordinates (and smaller y-coordinates if x values are equal) when distances are identical, each bucket’s list of points needs to be sorted with this custom comparator.
   • For a bucket with m points, sorting takes O(m log m) time. Summing this across all buckets gives us Σ(m_i log m_i) where the sum of all m_i equals N.
   • Mathematically, this sum has an upper bound of O(N log N): the worst case is when all points end up in a single bucket (all have the same distance to the origin), requiring a full O(N log N) sort. In better cases (points spread across many buckets), this sum will be smaller, but we typically use the worst-case upper bound for time complexity discussions.

3. Collect the top K points

   • We iterate through buckets in order of increasing distance, pulling points from each sorted bucket until we’ve gathered K points. This is an O(K) operation, since we stop as soon as we have our result set.

Final Time Complexity #

Adding these steps together, the overall time complexity is O(N log N). The dominant term here is the worst-case sorting of a single bucket containing all N points; the O(N) distance calculation and O(K) collection steps are negligible as N grows.

It’s definitely not O(KN log N)—there’s no nested operation that would multiply K with N log N. In best-case scenarios (points are perfectly spread across buckets with minimal sorting needed), the complexity could drop to O(N + K), but the standard worst-case upper bound we reference is O(N log N).

内容的提问来源于stack exchange，提问作者Sanket