Python3中已排序数组追加元素后调用sorted()的时间复杂度疑问

• 结论：这个操作的时间复杂度不是O(log n)，实际场景下是O(n)，而从通用算法复杂度的角度，我们通常会标注sorted()的时间复杂度为O(n log n)。
• 详细说明：
  • 你可能混淆了「在有序列表中插入元素」和「调用sorted()重新排序」的逻辑。sorted()不会只盯着新增的那个元素处理，它会对整个列表执行完整的排序流程——哪怕原列表几乎有序。
  • Python的sorted()底层用的是Timsort算法，它确实会利用列表里已有的有序片段来优化效率。在你说的场景里，原有序列表append新元素后，前n个元素是一个完整的有序段，新元素是单独的小片段，Timsort会直接合并这两个片段，这个过程只需要O(n)的线性时间。
  • 为什么达不到O(log n)？O(log n)是二分查找找位置的时间，但排序操作本身需要把所有元素处理一遍，光是把元素复制到新列表里就已经是O(n)的开销了，更别说合并的步骤。

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