Сегодня начнём разбирать большую компьютерную дисциплину — алгоритмы и структуры данных. В этой статье расскажем основы теории, а со следующей начнём решать задачи и писать алгоритмы в коде. Если вы во всём этом разберётесь и поймёте, то будете на голову выше всех, кто просто научился писать код, но не понимает, почему его нужно писать именно так.
Приступим.
Что такое алгоритмы в обычной жизни
С точки зрения обычного человека, алгоритмы — это любые пошаговые операции из реальной жизни. Это могут быть:
- получение паспорта;
- приготовление блюда по рецепту;
- процесс поступления в вуз или поиска работы;
- уборка квартиры;
- покупка машины.
Например, алгоритм заваривания чая можно описать так:
- Налить в чайник воды.
- Вскипятить воду в чайнике.
- Достать кружку.
- Открыть упаковку с чайными пакетиками.
- Положить в кружку новый чайный пакетик.
- Налить воду из чайника в кружку с пакетиком.
- Подождать 5 минут.
Сейчас программисты (и особенно — тестировщики) скажут, что в этом алгоритме много неточностей: не сказано, что нужно наливать воду именно из горячего чайника, что делать, если чай закончился, и всё такое. Ребята, успокойтесь — мы сейчас рассказываем про алгоритмы в жизни, там всё иногда чуть проще, чем в коде :)
👉 Короче, алгоритм — это какая-то последовательность действий, которая приведёт к нужному результату. Или не приведёт, если алгоритм составлен неверно. В программировании всё устроено точно так же: мы пишем последовательность команд для компьютера, и, если мы написали всё правильно, — получим какой-то результат. Если ошиблись — результат будет другой или программа не запустится.
Теперь взглянем на алгоритмы с точки зрения разработчиков.
Что такое алгоритмы с точки зрения программиста
Если взять формальное определение алгоритма и немного его упростить для понимания, то получится две части:
- Алгоритмы — это структурированные шаблонные решения задач при написании кода.
- И в то же время алгоритмы — это часть одной науки, которая называется «Алгоритмы и структуры данных».
Первая часть работает как в жизни: мы пишем какое-то решение, структурируем его, чтобы оно приводило к нужному результату, и всё это делаем на языке, понятном компьютеру. Проще говоря — это про написание кода по определённым правилам.
Структуры данных — это разные способы упорядочивания элементов в компьютерной памяти. Элементы можно объединять в стеки, очереди, списки, словари, кортежи и другие наборы, которые ещё называют коллекциями. Если интересно, почитайте наши статьи про такие коллекции:
👉 Алгоритмы в программировании — способ оптимальной работы со структурами данных для получения конкретного результата.
Например, у нас есть массив данных — список из 100 разных чисел, которые нам нужно упорядочить по возрастанию. Вот как может работать алгоритм в общих чертах:
- Программа проходит по списку из 100 элементов и выявляет число с наибольшим значением.
- После этого она переставляет это число — удаляет с текущей позиции и присваивает ему номер 100, то есть ставит в конец массива.
- Затем программа проходит по оставшимся 99 элементам в начале, снова находит наибольшее число и ставит его на позицию 99.
- Эти шаги повторяются до тех пор, пока число оставшихся элементов не уменьшится до единицы.
Если это перевести в код, а числа представить в виде столбиков (чем больше число, тем выше столбик), то работа алгоритма будет выглядеть так:
Если соединить всё вместе, то получается такая формула:
Алгоритмы + Структуры данных = Программы
Как часто применяются алгоритмы на практике
На самом деле мы все пользуемся алгоритмами в жизни, но не задумываемся об этом. Заварить чай — это алгоритм. Вызвать такси — тоже алгоритм со своей последовательностью действий. Даже спонтанная уборка в комнате или на рабочем столе у нас проходит по какому-то внутреннему алгоритму.
Программисты тоже пишут код по алгоритму, но не всегда думают о том, оптимальный ли это способ решения конкретной задачи. Мы сами написали много проектов без алгоритмов, и может показаться, что можно писать и без них. Всё так, но знание и понимание алгоритмов поможет вам решить задачу намного эффективнее. Для решения задачи можно применить 10 действий, если всё делать с нуля, или 3, если использовать уже готовые оптимальные решения и алгоритмы. Результат будет одинаковый, но с алгоритмами будет проще и круче.
Для применения алгоритмов не нужно сразу учить их все. Почти в любой задаче можно что-то оптимизировать, если посмотреть на неё свежим взглядом. Так появляются новые алгоритмы: программисты долго работают с какой-то программой и находят оптимальный способ её выполнения. Потом этот алгоритм можно описать, и другие тоже начнут его использовать.
Почти каждый код — это алгоритм для чего-то. Он может быть написан в несколько строк или занимать три экрана — объём тут не играет роли. Если в коде можно вывести какой-то новый паттерн, который можно использовать для других задач, появляется новый алгоритм. Каких-то правил и стандартов для написания новых алгоритмов не существует.
👉 Алгоритмы помогают решать задачи быстро, красиво и эффективно.
Почему говорят, что знать алгоритмы уже необязательно
Так говорят только две категории людей: те, кто не знают про алгоритмы вообще, и те, кто знает их настолько много, что применяет их уже не задумываясь. Когда смотришь на работу ребят из второй категории это выглядит как магия, но на самом деле человек так долго применял все изученные алгоритмы на практике, что ему уже кажется, что всё это происходит само, без паттернов и алгоритмов.
Иногда можно услышать или прочитать мнение, что алгоритмы могут спросить только на собеседовании, а в остальное время они не пригодятся.
На самом деле алгоритмы — сложная составная дисциплина, и в чистом виде действительно могут применяться не везде. Польза в том, что вы прокачиваете знание языка, умение логически мыслить и насмотренность, и в итоге сможете писать код быстрее и чище. После изучения уже выверенных практик вы поймёте, к чему нужно стремиться, и точно сможете применить эти знания на практике.
Каждому алгоритму — своя структура данных
Задача каждого алгоритма — получить нужный и предсказуемый результат. Чтобы алгоритм был более эффективным, знающие программисты выбирают для работы алгоритма подходящую структуру данных. Одни структуры лучше подходят для обработки множества чисел, другие — для оптимального поиска нужного значения, третьи — для быстрых вычислений и записи новых данных.
Мы собрали самые популярные у программистов структуры данных и их отличия друг от друга. Даже если вы сразу не запомните, что за что отвечает, — не переживайте. Просто постоянно практикуйтесь с разными алгоритмами и структурами, и в итоге вы будете сразу выбирать оптимальную структуру данных под свои задачи.
Массивы и списки — универсальная упорядоченная коллекция элементов. В них можно хранить строки, числа, объекты и любые другие структуры данных. В разных языках эти понятия немного различаются — например, иногда массив может хранить только элементы одного типа, а иногда разных.
Элементы можно добавлять, удалять, получать по номеру-индексу. Ещё по спискам можно проходить циклом — это операция, когда последовательно перебирает каждый элемент массива или списка и применяет к ним указанные действия.
Динамические массивы и списки позволяют автоматически управлять своим размером. При создании обычно появляется пустой массив и задаётся максимальное количество элементов. При превышении этого предела будет создаваться новый массив или список данных.
Стек позволяет создавать группы элементов по принципу LIFO (от слов last in, first out: последний пришёл, первый вышел). Это похоже на стопку тарелок: последнюю добавленную в стопку тарелку берут из неё первой.
Очередь — противоположность стеку и работает по принципу FIFO (first in, first out, то есть первый пришёл, первый вышел). В классическом варианте данные или задачи добавляются в конец очереди, а забираются из начала.
Есть ещё двусторонние очереди, когда данные можно добавлять и извлекать с обоих концов. В стеках и очередях элементы посередине недоступны.
Словарь, ассоциативный массив или карта. Информация в этой коллекции данных хранится в парах «ключ — значение». Ключи словарей должны быть уникальными, а значения могут повторяться.
Множество — то же самое, что классическое множество в математике. Это структура непронумерованных неповторяющихся данных, в которых можно искать пересечения, которые можно объединять, вычитать и над которыми можно выполнять остальные математические операции над множествами.
Деревья и графы. Это наборы связанных между собой ячеек данных и связей между ними — рёбер. Технически они реализованы как списки элементов со ссылками друг на друга, а визуально похожи на дерево или схему молекулы в химии. У дерева есть корневой узел, из которого появляются все остальные элементы. У графа корневого узла нет.
Самый простой вид дерева — двоичное, когда у каждого родительского узла может быть не более двух дочерних. На схеме ниже 5 — корневой узел:
Самые частые и популярные алгоритмы в программировании
Видов алгоритмов гораздо больше, чем структур данных, но если присмотреться, можно найти несколько самых популярных видов алгоритмов, которые чаще всего используются на практике.
Сортировка. Используется, когда данные в структуре надо расставить по какому-то признаку: величине, алфавиту, цене, частоте появления в датасете. Кроме пузырьковой сортировки, есть алгоритмы вставкой, выбором, слиянием, расчёской и ещё десяток других.
Поиск. Алгоритм, который ищет и находит нужный элемент структуры. Самый простой алгоритм поиска двоичный: он делит массив данных на половины, и искомый элемент сравнивается с серединой этого массива. Если совпадение найдено, поиск заканчивается. Если не найдено, берётся та половина массива, в которой должен находиться элемент.
Например, мы ищем в массиве из 16 возрастающих чисел число 37. Сначала алгоритм проверит середину массива, восьмое по счёту число. Если оно не совпадает с искомым элементом, программа скорректирует поиск: если восьмое число больше нужного, мы возьмём левую часть списка. Если меньше — правую. Потом переходим к нужной половине массива и проверяем средний элемент уже оттуда.
Такой алгоритм называется двоичным, или бинарным, поиском:
Алгоритмы обхода деревьев и графов. Используются для проверки всех узлов и рёбер в деревьях и графах.
Самые известные среди алгоритмов обхода — поиск в глубину и поиск в ширину.
Жадные алгоритмы делают на каждом шаге оптимальный выбор из всех доступных. Их идея в том, что конечный результат тоже должен оказаться оптимальным. Пример: алгоритм Дейкстры в навигаторах ищет на каждом шаге самый короткий путь для построения самого быстрого маршрута.
Реализация алгоритма Дейкстры для обхода всех вершин графа по самым коротким путям:
Рекурсия — функция, которая запускает сама себя несколько раз, пока не начнёт выполняться какое-то условие. Это происходит так:
- Рекурсия запускается в первый раз.
- Проверяет условие для перехода к финальному шагу.
- Если условие не выполняется, рекурсия изменяет один из параметров программы, сохраняет промежуточный результат и заново начинает выполнение себя.
- Снова проверяется условие для перехода к финальному шагу.
- Это повторяется до тех пор, пока это условие не будет выполняться, например, на пятом шаге.
- После этого последовательно выполняются все предыдущие шаги с сохранёнными результатами.
Так работает функция подсчёта факториала числа, то есть произведение всех чисел от единицы до самого числа. Мы последовательно уменьшаем передаваемое в функцию число и сохраняем общее произведение, пока не дойдём до 1:
Сложность алгоритмов
Скорость работы алгоритма оценивается по тому, как растёт время его работы в зависимости от количества входных данных. Чтобы программист мог заранее примерно понять, как долго по времени будет работать его алгоритм, используют оценку сложности.
Самая известная оценка сложности алгоритма называется Big O, или О-нотацией. Скорость роста указывается в скобках после буквы О и расшифровывается так:
- О(1) — постоянная скорость, не зависящая от входных данных. Например, постоянная скорость работы будет у алгоритма, который извлекает элемент из списка по индексу.
- О(log n) считается как степень, в которую нужно возвести 2 для получения числа n. Например, O(log n) при n равном 128 будет равно 7. Получается, что при 128 разных входных элементах алгоритм найдёт решение за 7 шагов.
- O(n) ещё называется линейной оценкой. Сколько входных данных, столько шагов займёт работа.
- О(n * log n) — линейно-логарифмическая сложность. Для получения количества шагов алгоритма нужно перемножить две предыдущих формулы.
- О(n^2) — квадратичная сложность. Число шагов равно квадрату входных данных.
- О(n^3) — кубическая сложность. Для результата нужно сделать столько шагов, равное кубу количества входных элементов.
- О(n!) — факториальная сложность, самый медленный вариант. Число шагов равно факториалу количества входных данных.
👉 Во всех этих оценках n – это количество элементов в структуре данных, которую использует алгоритм.
С чего начать
Алгоритмы — одна из самых популярных тем в программировании, и одна из самых неизменных. За 50 лет логика работы компьютеров осталась прежней, и многие книги до сих пор остаются полезными, вот несколько из них.
Книги:
- «Алгоритмы и структуры данных» Никлауса Вирта.
- «Алгоритмы: построение и анализ» Томаса Кормена.
- «Алгоритмы на Java» Роберта Седжвика.
Если вам интересно больше узнать про основные структуры данных, прочитайте статью Яндекс Практикума.
Чтобы прочувствовать на себе всю мощь алгоритмического подхода в программировании, приходите в Практикум на курс «Алгоритмы и структуры данных». Там есть бесплатная часть, а после прохождения курса вы сможете сами придумывать новые алгоритмы, которые будут работать быстрее и эффективнее.
Что в следующий раз
Со следующей статьи начнём разбирать конкретные алгоритмы. Для начала возьмём алгоритмы сортировки — зачем они нужны в жизни и почему программисты уделяют им так много времени.
