Вставка в начало списка Python внутри цикла: во что превращается сложность
Коллега собирает перевёрнутую копию списка так:
def reverse_copy(items):
out = []
for x in items:
out.insert(0, x)
return out
На списке из 200 000 элементов функция работает недопустимо долго. Какая асимптотика по времени у этого кода относительно длины входа n?
- O(n) — цикл проходит по списку ровно один раз
- O(n log n) — список периодически перевыделяет память
- O(log n) — вставка ищет позицию двоичным поиском
- O(n^2) — каждая вставка в начало сдвигает уже накопленные элементы