np.argsort()时间复杂度及两种切片写法的内存消耗差异确认

1. np.argsort() 的时间复杂度 #

np.argsort() 底层采用Timsort排序算法（与Python内置sort逻辑一致），平均和最坏时间复杂度均为O(n log n)，其中n为输入数组的元素数量。Timsort是稳定的自适应排序算法，在处理部分有序的数组时会有额外性能优化，但整体复杂度仍维持在O(n log n)级别。

2. 两种切片写法的内存占用差异 #

导师的说法是正确的，两者内存占用确实存在明显差异：

• np.argsort(array)[::-1][:10]：执行流程为：
  1. 先生成长度为n的完整排序索引数组；
  2. [::-1]会创建一个全新的、长度为n的逆序索引数组（这一步是内存占用的关键）；
  3. 最后取前10个元素。
     整个过程中会产生一个完整的逆序中间数组，额外内存开销为O(n)。
• np.argsort(array)[-10:]：执行流程为：
  1. 生成长度为n的完整排序索引数组；
  2. 直接从原索引数组的末尾截取最后10个元素，不会创建完整的逆序数组。
     额外内存开销仅为存储10个元素的空间，即O(1)级别的常数开销。

额外优化建议 #

如果仅需要获取数组中最大10个元素的索引，更高效的写法是使用np.argpartition(array, -10)[-10:]：

• np.argpartition的时间复杂度为O(n)，远低于argsort的O(n log n)；
• 该方法返回的10个索引是无序的，若需要按降序排列，可再对这10个索引执行一次小范围排序（时间复杂度O(10 log 10)，几乎可以忽略），整体性能比全排序后切片更优。

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