Если я удалю один элемент из массива с помощью splice() следующим образом:
arr.splice(i, 1);
Будет ли это O(n) в худшем случае, потому что он сдвигает все элементы после i? Или это постоянное время, с какой-то связанной магией списка?
Какова временная сложность array.splice() в Google Chrome?
Ответ 1
В худшем случае должен быть O(n) (копирование всех элементов n-1 в новый массив).
Связанный список будет O(1) для единственного удаления.
Для тех, кого это касается, я сделал этот лениво-обработанный тест. (Пожалуйста, не запускайте в Windows XP/Vista). Как вы можете видеть из этого, он выглядит довольно постоянным (т.е. O(1)), поэтому кто знает, что они делают за кулисами, чтобы сделать это безумным. Обратите внимание, что независимо, фактический splice ОЧЕНЬ быстрый.
Повторное использование расширенного теста непосредственно в оболочке V8, предлагающей O(n). Обратите внимание, что вам нужны огромные размеры массива, чтобы получить время выполнения, которое может повлиять на ваш код. Это следует ожидать, если вы посмотрите на код V8, который он использует memmove для создания нового массива.