Выбор ответа Junior Коллекции спрашивают часто обновлено
Сложность insert(0) у списка
Вопрос
Какая сложность у lst.insert(0, x) для списка из n элементов?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(n). list это массив указателей, и вставка в начало сдвигает все n элементов на одну позицию: O(n).
Варианты ответа
- O(1)
- O(log n)
- O(n)правильный ответ
- O(1) амортизированно
Разбор
list это массив указателей, и вставка в начало сдвигает все n элементов на одну позицию: O(n). O(1) амортизированно это про append в конец, где лишь изредка происходит перевыделение памяти. Для частых вставок и удалений с обоих концов есть collections.deque.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.