Если бы вашим первым языком программирования был Javascript, как это было у меня, то вы могли бы немного потеряться в самом названии. Вы не услышите термин «статический» или «динамический», когда речь идет о массивах в Javascript.

Так в чем именно разница между этими двумя?

Начнем с понимания того, что такое статический массив. Техническим определением будет реализация массива, который выделяет фиксированный объем памяти, используемый для хранения значений массива. При фиксированном объеме памяти это означает, что нет места для добавления каких-либо значений в тот же массив. Как ни странно, добавление значений в массив — одна из самых распространенных вещей, которые вы будете делать, так что же происходит? На самом деле довольно просто... Вы находите больший слот памяти, копируете все значения, а затем добавляете то значение, которое хотите. Звучит некрасиво, но не все так плохо, об этом позже. Мы также рассмотрим, что это означает с точки зрения Большого О.

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

Изучая Javascript, я был избалован тем, что просто определял массив как переменную и манипулировал им, как мне было нужно. Причина в том, что Javascript использует динамические массивы. Даже когда ваш массив заполняет это дополнительное пространство, вам не нужно ничего делать. Javascript под капотом найдет место в памяти, выделит удвоенный объем памяти, необходимый для хранения ваших исходных значений, а также новых, и скопирует значения.

На данный момент вы можете увидеть разницу между ними по определению, но какое вам дело?

Вот где все становится действительно круто. Давайте поместим некоторые из этих определений в визуальное представление и посмотрим, что все это на самом деле означает.

Вот несколько операций, которые вы будете выполнять с массивами, а также их временные сложности.

  • Доступ к значению по заданному индексу: O(1)
  • Вставка значения в начале: O(n)
  • Обновление значения по заданному индексу: O(1)

Это справедливо как для статических, так и для динамических массивов. Они отличаются, когда вы хотите вставить значение в конец массива.

Давайте рассмотрим пример того, как статические массивы занимают память. Для простоты каждое значение в массиве занимает в памяти на этой диаграмме 1 блок. Вы могли бы уточнить и говорить о байтах памяти в зависимости от типа данных элемента, но это сделало бы этот график слишком большим.

В приведенном ниже примере мы начинаем с массива, содержащего значения [ 1, 2 ], которые вы увидите фиолетовым цветом. Что ж, я хочу добавить еще одно значение… Отлично, все, что нужно сделать вашему компьютеру, — это найти новую память, соответствующую вашим текущим значениям, плюс значение, которое вы хотите добавить. И давайте сделаем это снова, потому что сейчас нам нужно добавить значение 4.

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

Когда вы начинаете строить алгоритмы с учетом пространственной и временной сложности, вы хотите найти лучший способ сделать что-то с наиболее оптимальной сложностью.

Ранее я говорил, что динамический массив выделяет вдвое больше памяти, что значительно упрощает добавление значений. Вот как это выглядит.

Здесь мы начинаем с того же массива [ 1, 2 ], но когда он инициализируется, он выделяет в памяти 4 блока (вдвое больше размера исходного массива). Теперь при добавлении значений 3 и 4 потребуется только O(1) времени для каждого, и нам не нужно искать больше памяти, пока мы не добавим пятое значение, которое тогда составляет O(n) времени. Чтобы быть более конкретным, этот массив может изменяться в размере без необходимости копировать себя каждый раз, пока он находится в пределах выделенной памяти. Если вы подумаете о том, как часто вы добавляете значения в массив, вы можете себе представить, как это может повлиять на ситуацию. После создания нашего последнего массива со значениями 1–5 у нас остается память для этих 5 значений, а также 5 пустых полей, которые еще не определены. Теперь каждый раз, когда мы добавляем значение в конец, это займет O(1) времени, если оно находится в пределах выделенного пространства.

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

Давайте посмотрим краткое изображение, чтобы понять, как выглядит O(n) по сравнению с O(1).

Массивы — одна из лучших структур данных, несмотря на то, что они довольно просты. Я надеюсь, что теперь вы немного лучше понимаете их основы и можете оценить, как язык высокого уровня, такой как Javascript, помогает упростить работу. Javascript — не единственный язык, который делает это, Python также по умолчанию использует динамические массивы. В таких языках, как C, C++ и Java, вы создаете массивы, а также определяете объем памяти, который вы хотите выделить для них.