Большой O массивов JavaScript

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

какую производительность (с точки зрения большой сложности времени O) я могу ожидать от реализаций JavaScript в отношении производительности массива?

Я полагаю что все разумные реализации JavaScript имеют по крайней мере следующие большого.

  • Access-O (1)
  • добавление-O (n)
  • добавление-O (n)
  • вставка-O (n)
  • удаление-O (n)
  • Замена-O (1)

JavaScript позволяет предварительно заполнить массив до определенного размера, используя new Array(length) синтаксис. (Бонусный вопрос: создает массив таким образом O (1) или O (n)) это больше похоже на a обычный массив, и если он используется в качестве предварительно определенного размера массива, может разрешить добавление O(1). Если круговая буферная логика добавлена, вы можете достичь O(1) prepending. Если используется динамически расширяющийся массив, O (log n) будет средним случаем для обоих из них.

могу ли я ожидать лучшей производительности для некоторых вещей, чем мои предположения здесь? Я не ожидаю, что что-то изложено в каких-либо спецификациях, но на практике может быть, что все основные реализации используют оптимизированные массивы за кулисами. Являются там динамически расширяющиеся массивы или некоторые другие алгоритмы повышения производительности на работе?

П. С.

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

2 80
javascript arrays algorithm time-complexity big-o

2 ответа:

В отличие от большинства языков, которые реализуют массивы с, ну, массивы, в Javascript массивы являются объектами, а значения хранятся в хэш-таблице, как и обычные значения объектов. Как таковой:

  • Access-O (1)
  • добавление-амортизированный O(1) (иногда требуется изменение размера хэш-таблицы; обычно требуется только вставка)
  • добавление-O (n) через unshift, Так как это требует переназначения всех индексов
  • Вставка - Амортизированная O (1) если значение не существует. O (n) если вы хотите изменить существующие значения (например, используя splice).
  • удаление-амортизированный O (1) для удаления значения, O(n) если вы хотите переназначить индексы через splice.
  • Замена-O (1)

В общем случае установка или отмена любого ключа в dict амортизируется O (1), и то же самое касается массивов, независимо от того, что такое индекс. Любая операция, требующая перенумерации существующих значений, является O (n) просто потому, что вам нужно обновить все затронутые значения.

88

все сложности, о которых вы упомянули, кажутся прекрасными. Но если объект массива поддерживает длину, то добавление также может быть выполнено за O(1) Время.

-4