Какова временная сложность некоторых операций со списком python?

Question

Я знаю, что это какой-то базовый c вопрос, но я не разбираюсь в фундаментальных вещах. Я знаю только, что для метода stack pop () последний элемент выскакивает за время O (1).

В python разрешено вставлять любую позицию в списке, а также вставлять элемент в любую позицию, например, list.pop(index) и list.insert(index, item). Если длина списка n, какова их средняя временная сложность?

Кроме того, есть ли разница между list.insert(index, item) и list = list[:index] + [item] + list[index:]?

Большое спасибо в помощь!

Answer 1

Хотя list.insert(index, item) делает практически то же самое, что list = list[:index] + [item] + list[index:], встроенная функция python list.insert была создана как более быстрый способ вставки элемента в список. list.insert является более продвинутым, а не эквивалентно list = list[:index] + [item] + list[index:], потому что он использует другой алгоритм и намного быстрее.

Временная сложность составляет O (n), что примерно равно n /2.