Какова сложность операции push в массиве
Что проверяют
Знаете ли вы разницу между «в среднем» и «амортизированно» и понимаете ли, откуда берётся редкое дорогое добавление. Следом обычно спрашивают про unshift, про concat и про цену иммутабельного добавления в состоянии React.
Как отвечать
Правильная формулировка: push работает за амортизированное O(1). Отдельная операция может стоить O(n), но суммарная стоимость n добавлений линейная, поэтому в пересчёте на одну операцию выходит константа.
Механика на примере V8. У массива есть хранилище с запасом ёмкости. Пока запас есть, push пишет значение в следующую ячейку и увеличивает length. Когда место кончилось, движок выделяет хранилище примерно в полтора раза больше и копирует туда все элементы, это O(n). Ёмкость растёт геометрически, копирования случаются всё реже, и их общая стоимость ограничена величиной порядка n. Если бы хранилище росло на фиксированное число ячеек, амортизированная стоимость стала бы O(n).
Уточнения, которые показывают опыт:
- несколько аргументов:
push(a, b, c)стоит O(k) от числа добавляемых элементов; - спред:
arr.push(...big)передаёт каждый элемент отдельным аргументом, и на массиве в сотни тысяч элементов можно получитьRangeErrorо переполнении стека. Большие массивы сливают циклом или черезconcat; unshift: добавление в начало сдвигает все элементы, это O(n);- иммутабельность: в React и Redux добавляют через
[...prev, item], это копия за O(n). Один раз это нормально, но в цикле из n итераций выходит O(n²), поэтому пачку собирают отдельно и кладут в состояние одним обновлением.
Где спотыкаются
Отвечают просто «O(1)» без слова «амортизированно». Следующий вопрос будет про момент, когда хранилище переполнено, и без понимания механики ответ не собрать.
Или наоборот называют push операцией O(n) из-за перевыделения памяти, путая худший случай одной операции с оценкой всей последовательности.
Строят очередь на push и shift, считая обе операции дешёвыми. Удаление из начала требует сдвига, и движок не обещает, что оно будет константным, поэтому для больших очередей делают кольцевой буфер или хранят индекс головы поверх массива.