Выполнение следующего в консоли WebKit (в Chrome или Safari) занимает ~ 200 мс.Запустив тот же код с номерами, меньшими 50855, вы получите примерно линейное время O ( n ).(Например, с 1e4 вы получите ~ 40 мс.)
Однако, измените это значение на 50856 - просто с шагом 1 - и во время работы произойдет огромный скачок (до ~ 600 мс на моем 13-дюймовом AlMBP, больше похоже на ~ 2s на старой машине Debian).После этого время работы кажется экспоненциальным O (2 n ): удвоение с 50856 до 1e5 приводит к ~ 2 с на Mac, что примерно в 3,2 раза больше по сравнению с ~ 600 мс,и удвоение снова до 2e6 дает ~ 10-кратное увеличение.(Обратите внимание, что 3.2 2 ≈ 10.)
В Opera Dragonfly и в консолях Firebug время работы довольно четко квадратично O ( n 2 ), как и ожидалось (так как при этом происходит сращивание n раз, когда каждое соединение включает смещение n элементов в массиве).
... что такое WebKitделать?
var start = +new Date, a = [];
for(var i = 0; i < 50855; i++)
a[i] = i;
for(var i = 0; i < a.length; i++)
a.splice(i--, 1);
+new Date - start
Если вам не хочется использовать консоль: http://jsfiddle.net/CVgSt/ Такое же поведение, хотя в WebKit постоянные коэффициенты в несколько раз меньше, чем в консоли.