面试题：Python中sorted在自定义排序逻辑下的深度应用

Question

假设有一个列表points = [(1, 4), (3, 2), (5, 5), (2, 3)]，表示二维平面上的点。请使用sorted函数按照点到原点 (0, 0) 的距离（欧几里得距离）对列表进行升序排序。请提供实现代码，并分析该排序过程的时间复杂度。如果要优化时间复杂度，在不改变排序结果的前提下可以采取哪些措施？

Answer 1

import math

points = [(1, 4), (3, 2), (5, 5), (2, 3)]
sorted_points = sorted(points, key=lambda point: math.sqrt(point[0]**2 + point[1]**2))
print(sorted_points)

时间复杂度分析

sorted函数在Python中通常使用的是Timsort算法，它的平均时间复杂度是 $O(n log n)$，其中 n 是列表中元素的个数。这里计算每个点到原点的距离以及作为排序依据的过程，时间复杂度为 $O(n)$，因为要对每个点都计算一次距离。因此，整个排序过程的时间复杂度主要由排序算法决定，为 $O(n log n)$。

优化措施

1. 避免重复计算平方根：由于排序只关心距离的相对大小，而不是具体值，可以直接比较距离的平方，这样可以避免对每个点都计算平方根，计算距离的时间复杂度降为 $O(n)$，但整体排序的时间复杂度依然是 $O(n log n)$，因为排序算法本身的复杂度未变。

points = [(1, 4), (3, 2), (5, 5), (2, 3)]
sorted_points = sorted(points, key=lambda point: point[0]**2 + point[1]**2)
print(sorted_points)

2. 对于大规模数据：如果数据量非常大，可以考虑使用并行计算的方式，利用多核心CPU并行计算距离，然后再进行排序。这可以在一定程度上减少计算距离的时间，但实现相对复杂，并且由于Python的GIL（全局解释器锁），对于CPU密集型任务并行效果可能有限。