python - 为什么这个解决方案的复杂度为 O(nlogn)？

Question

给定一个整数数组，返回一个新数组，其中每个元素新数组是其右侧较小元素的数量原始输入数组中的元素。例如，给定数组 [3, 4, 9, 6, 1]，返回 [1, 1, 2, 1, 0]。

import bisect

nums = list(input().split())
nums_to_the_right = []
result = []
sorted_nums = []

for num in reversed(nums):
    index = bisect.bisect_left(sorted_nums, num)
    result.append(index)
    bisect.insort(sorted_nums, num)

result.reverse()
print(result)

此代码打印正确的结果。 bisect_left 函数应返回索引，当前元素必须具有该索引才能对数组进行排序。 insort 函数将元素放入数组中，使数组保持排序状态。我预计整段代码的复杂度为 O(n^2)，但据说需要 O(nlogn) 才能工作。请告诉我为什么？

Answer 1

bisect 模块使用 binary search algorithm找到插入索引。使用此算法的每次插入的复杂性 - O(logn) (您可以通过以下链接阅读非常详细的描述)。您有 n 个元素，因此最终复杂度为 O(nlogn)。最终 result.reverse() 复杂度为 O(n)，因此在汇总复杂度计算中可以将其省略。