Почему это решение имеет 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) , поэтому ее можно опустить в вычислении суммарной сложности.