какова временная сложность array.splice (... array.splice ())

Question

Я решал один из вопросов leetcode - вращающийся массив. Я решаю с помощью O (N), используя два для l oop, но тогда мое время выполнения было ниже, чем это решение.

Мое решение: время выполнения 80 мс

var rotate = function(nums, k) {

    let a = Array.from({length:nums.length})

    for (let i = 0; i < nums.length; i++) {
      a[(i + k) % nums.length] = nums[i];
    }
    for (let i = 0; i < nums.length; i++) {
      nums[i] = a[i];
    }


};

Другое решение: время выполнения 52 мс

var rotate = function(nums, k) {
      return nums.splice(0,0,...nums.splice(nums.length - k))
};

как это возможно. Насколько я знаю, сращивание - это O (N), и в этом решении сращивание также снова используется в сращивании. Значит, это решение должно быть O (N2), и мое решение должно быть быстрее, чем это?

Answer 1

Array#splice - это O (n), потому что он может сдвигаться до каждого элемента массива за один вызов. См .: Какова временная сложность array.splice в Google Chrome?

При определении временной сложности алгоритма, если каждый O (n ) операция выполняется последовательно, и количество операций O (n) является постоянным множителем (что и имеет место здесь), это все еще O (n). O (n ² ) - следствие вложенных циклов; то есть для каждого n мы выполняем еще одну операцию O (n).

Этот код использует только два последовательных вызова Array#splice вместе с O (n) спредом, всего O (3n) что эквивалентно O (n).

«Моя среда выполнения была медленнее» - Сложность времени и время выполнения - совершенно разные вещи. Большая часть времени выполнения зависит от деталей реализации, фиксированных накладных расходов (постоянные коэффициенты), которые игнорируются большой буквой O, размера тестовых примеров L C, состава тестовых примеров, неточностей тестового примера L C измерение, et c. Для большей уверенности используйте тест под вашим собственным контролем на очень больших случайных входных данных. Два кода O (n) редко демонстрируют идентичные характеристики производительности - временная сложность связана только со скоростью роста алгоритма.

Что касается этого конкретного сравнения, имейте в виду, что встроенные функции сильно оптимизированы. Я предполагаю, что это работает в NodeJS (V8), поэтому многие встроенные функции написаны на C ++ (или Torque) (и V8 в этом не уникален).

Реализация встроенных функций на более низком уровне означает, что память, вероятно, будет компактной и обычной , поэтому доступ к кеш-памяти выигрывает от локальности , меньше погоня за указателем, возможности для распределения стека , et c. for циклы в коде высокого уровня сложнее оптимизировать. Они включают индексные переменные, выполнение сравнений, ветвление и т. Д., Все из которых необходимо эффективно преобразовать в байт-код таким образом, чтобы это могло быть неоптимальным. В случаях, когда встроенная реализация находится в JS, дизайнеры проделали большую работу, чтобы сделать их максимально эффективными.

В случае Array#splice это записано в Torque что переведено на эффективную сборку .

В вашем коде let a = Array.from({length:nums.length}). Влечет за собой накладные расходы на выделение памяти для двух объектов.

Вкратце: сравните результаты справедливо, не смешивайте сложность и скорость и используйте встроенные функции, когда это возможно (используйте профилировщик для определения редких случаев, когда этого не следует делать).