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模块使用二分查找算法查找插入索引。使用此算法的每次插入的复杂性 - O(logn)（您可以通过链接阅读非常详细的描述）。你有n 个元素，所以最终的复杂度是O(nlogn)。最终result.reverse()复杂度为O(n)，因此在汇总复杂度计算中可以省略。