Одна из простейших задач, которую может решить компьютер, - это арифметика. Одно число плюс / минус другое - это простое включение и выключение «лампочек» в компьютере, чтобы в конечном итоге представить окончательную сумму или разницу. А простота и легкость, с которой компьютеры могут выполнять арифметические операции, делают поиск в массивах простым и эффективным. Но сначала массив ...
Массив на нижнем уровне представляет собой блок непрерывной памяти, который выделяется для хранения информации, и непрерывность здесь является ключевым аспектом этого распределения памяти, которое обретет смысл через минуту. Не вдаваясь в обсуждение строго типизированных и динамически типизированных языков, давайте предположим, что мы объявили массив, способный хранить 10 символов или другие биты информации, и в него мы поместили наши 10 символов, или, в данном случае, числа.
arr = [34,12,8,100,6,22,132,657,98,33]
Наша переменная arr сохраняет место в памяти нашего массива, так что нам, программисту, не нужно запоминать его самим. (Это, конечно, один из основных моментов переменных.) Позже, когда мы хотим извлечь значение по определенному индексу, которое будет использоваться для чего-то, мы сделаем это, используя скобки. Например, мы можем сказать компьютеру, чтобы он получил значение индекса 2 массива, который находится по адресу, который мы сохранили в arr, следующим образом:
arr[2] //go to the third element of the array -> 8
Легкий. Простой. Но как именно это работает и, что более важно, насколько оно постоянное и, следовательно, эффективное? Что ж, математика, и в частности математика, стала возможной благодаря вышеупомянутой непрерывности выделения памяти массива ...
Когда мы набираем arr[2], на самом деле мы говорим: «Перейдите в ячейку памяти переменной arr. Затем, начиная с этой отправной точки, переместитесь на 2 позиции в памяти и дайте мне то, что там живет ». Таким образом, выражаясь в математических терминах, мы говорим компьютеру дать нам значение, которое находится в «начале arr + 2».
Если бы вместо этого мы сказали компьютеру дать нам arr[8], он бы, следуя той же схеме, просто перешел бы к началу блока памяти, который был выделен для массива, который он сохранил в переменной arr, а затем просто продвинуться вперед на 8 делений.
Как видите, непрерывность выделения памяти для массивов делает поиск значения в массиве делом простой арифметики, которая в терминах Big O имеет порядок 1 или константу. Компьютер просто должен математически перейти к той ячейке памяти, которую программист предоставляет в скобках на основе местоположения в памяти начала массива, и компьютер знает, что он может это сделать, потому что массивы являются непрерывными блоками памяти.
Это может показаться тривиальным делом, и в некоторых отношениях это так. Но при работе со сложными алгоритмами, программами и проблемами учет времени выполнения может быть невероятно важным, и знание большого числа определенных действий позволяет рассчитать время выполнения. Итак, продвигаясь вперед, вы можете знать, что попросить ваш компьютер получить значение в индексе массива тривиально в общей схеме алгоритмической среды выполнения и о чем вам не стоит беспокоиться при работе над оптимизацией кода.
