Возможно, вы слышали или не слышали термин структуры данных и алгоритмы раньше. Если вы занимаетесь информатикой, держу пари, что да. Для кого-то незнакомого эти слова кажутся техническими и пугающими. В мире разработки программного обеспечения пути пересечения с этим в конечном итоге неизбежны, и я считаю, что размышления и практика в этих терминах составляют разницу между разработкой кода, который просто работает, и разработкой кода, который эффективен. В этой статье будет определен каждый термин, за которым следует краткое описание нотации большой О. Поскольку эта тема может интересовать или не интересовать большинство из вас, я принял решение использовать старое аниме «Большой О» в качестве последовательной точки отсчета, например, для аналогий.
Структуры данных, что это такое?
Структура данных — это способ хранения и организации информации (т. е. данных), который обеспечивает эффективный доступ к ней и управление ею. Структуры данных широко используются в программной инженерии и компьютерных науках. Скорее всего, если вы только начинаете изучать программирование, вы уже работали с ними целым рядом. Объем и разнообразие всех различных структур данных в отношении разработки программного обеспечения огромны, но вот две наиболее общие структуры данных:
- Массив: данные организованы в скобках в последовательном порядке. Каждая запись данных в этих скобках называется элементом и отделяется запятой. Доступ к этим элементам можно получить с помощью пронумерованных индексов, которые начинаются с 0 и увеличиваются при каждом вводе данных. Пример Javascript:
> catchPhrase[0] "Big"
- Хеш: данные организованы в фигурных скобках с ключом, указывающим на значение. Эти пары ключ/значение обычно разделяются запятой. Доступ к данным (значению) можно получить по его ключу. Это имеет то преимущество, что имеет постоянную контрольную точку для доступа к указанному значению. Синтаксис для этого различается в разных языках, и в Javascript это называется объектом. Вот пример Javascript:
> characters['Android'] "Dorothy"
Что такое алгоритм?
Алгоритм — это процедура или процесс, который вы используете для решения проблемы или выполнения задачи. В следующем разделе мы рассмотрим, как алгоритмы классифицируют свою эффективность, используя нотацию Big O. Мы можем использовать аналогию для общей задачи в качестве примера алгоритма. Общей задачей является создание гигантского робота для борьбы с преступностью, как в сериале, на который я, к сожалению, решил постоянно ссылаться. Вот теоретические шаги:
- Быть Брюсом Уэйном, эсквайром. миллиардер.
- Либо отправляйтесь в школу по созданию гигантских роботов, либо наймите кого-нибудь, у кого есть.
- Купите необходимые инструменты и материалы.
- Соберите робота в стиле Gundam Wing или наймите для этого кого-нибудь.
В качестве примера, более тесно связанного с компьютерным программированием, я выбрал функцию Javascript, которая находит индекс в массиве, соответствующий заданному элементу. Если элемент не найден, возвращается false. Потому что эта функция — это «как» этой задачи. Функция ЯВЛЯЕТСЯ алгоритмом, и в этом примере я попытаюсь использовать как массив, так и хэш-структуру данных:
> findIndexOfElement("Showtime!")
2
> findIndexOfElement("Not Present")
false
Этот пример был немного сложным, но, надеюсь, вы уловили идею и сможете следовать объяснениям, данным в каждой строке комментария, обозначенной //. Также в этом примере не учитываются повторяющиеся элементы, и если это так, эта функция всегда будет возвращать последний индекс повторяющегося элемента в массиве.
Краткое описание нотации Big O
В компьютерных науках нотация Big O используется для описания времени выполнения или памяти, необходимой для выполнения алгоритма в худшем случае. Поскольку при записи времени, необходимого для выполнения конкретного алгоритма, в игру вступают многие факторы, нотация Big O НЕ является просто средним значением эталонных времен выполнения, записанных для выполнения алгоритма. Вместо этого это метрика того, насколько быстро растет время выполнения по отношению к входным данным, чтобы прийти к желаемому выводу.
Синтаксис этой нотации не очень интуитивен, но я сделаю все возможное, чтобы объяснить. В нотации большого о "о" обозначает порядок величины, который является ссылкой на класс шкалы любого числового значения, в котором каждый класс содержит значения фиксированного отношения к классу, предшествующему ему. Примером этого может служить сравнение веса гигантского робота с весом человека. В котором вес гигантского робота можно описать как на много порядков превышающий вес человека. "n" в большой нотации o обычно представляет размер входных данных, таких как массив, содержащий один элемент, или массив, содержащий тысячи элементов. Я действительно хотел привести здесь еще одну отсылку к аниме, но подумал, что пощажу вас только один раз.
Вот несколько примеров большой нотации o (с использованием Javascript в качестве ссылки):
- Постоянное время или O(1) алгоритм имеет постоянное время выполнения относительно его входных данных. Как правило, это то, что можно сделать за один «шаг».
- Linear Time или O(n) время выполнения алгоритма увеличивается относительно размера его входных данных. В общем это какая-то базовая итерация
- Квадратичное время или O(n²) время выполнения алгоритма увеличивается относительно размера его входных данных в квадрате. Обычно это включает циклическую итерацию
Заключение
Структура данных, которую вы используете, и алгоритм, который вы разрабатываете, могут сильно различаться, но имеют значение. Некоторые структуры данных лучше подходят для организации определенного набора данных, чем другие, и важно начать думать в терминах большой нотации при разработке алгоритмов для решения проблем. Это не только принесет пользу вам как разработчику программного обеспечения, но и сделает ваш код кратким и эффективным.
