Что такое алгоритм

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

Посмотрим на примере навигатора: алгоритм проверяет перекрёстки, отбрасывает тупиковые направления и в конце восстанавливает найденный маршрут:

Разбор кода, поиск записи и построение маршрута – совершенно разные задачи. Но во всех случаях программе нужен точный способ получить результат.

Недостаточно сказать компьютеру «найди лучший маршрут» или «найди нужный элемент». Нужно определить последовательность действий.

Такой способ решения задачи называется алгоритмом.

Начнём с простой задачи. Есть набор чисел:

Нужно найти самое большое число.

Мы сразу видим ответ – 9. Но программа не может просто посмотреть на весь набор и догадаться, какой элемент максимальный. Ей нужен способ, который будет работать не только с этими пятью числами, но и с любым другим набором.

Например, можно хранить самое большое число из уже просмотренных и постепенно проходить по всем элементам. Запишем эту идею псевдокодом:

Псевдокод похож на обычную программу, но не принадлежит какому-то конкретному языку. Он нужен, чтобы показать саму идею решения без особенностей JavaScript, Python, Java или C++.

Посмотрим, как этот алгоритм работает на нашем наборе:

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

Эти понятия связаны, но означают разное.

Задача описывает результат, который нужно получить. В нашем случае – найти максимальное число в наборе.

Алгоритм описывает способ получить этот результат. Мы решили проходить по элементам и хранить самое большое из уже просмотренных чисел.

Код – это уже реализация алгоритма на конкретном языке программирования. Один и тот же алгоритм можно написать на JavaScript, Python, Java или C++: запись будет отличаться, а идея останется той же.

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

Представим другую задачу. Нужно найти число 37 в отсортированном массиве:

Самый простой вариант – начать с первого элемента и проверять числа по очереди:

Такой способ работает: шесть проверок, и число найдено.

Но мы знаем про этот массив кое-что ещё: числа расположены по порядку. Значит, этим можно воспользоваться. Возьмём элемент в середине и сравним его с тем, что ищем – одно сравнение сразу скажет, в какой половине искать дальше.

Сейчас нам не нужно разбираться во всех деталях этого алгоритма. Важно другое: первая стратегия проверяет элементы один за другим, а вторая умеет сразу отбрасывать целые части массива.

Обе решают одну задачу, но делают это по-разному. Поэтому в алгоритмах нас интересует не только правильный ответ, но и то, как именно мы к нему пришли.

Представим, что мы написали такой алгоритм поиска максимального числа:

Проверим его на массиве:

Алгоритм вернёт:

Всё работает правильно. Но попробуем другой набор данных:

Ни одно из чисел не больше 0, поэтому значение max так и не изменится. Алгоритм вернёт:

Хотя 0 вообще нет в массиве, а правильный ответ:

Проблема в том, что алгоритм не учитывает случай, когда все числа отрицательные. На первом примере ошибка просто осталась незаметной.

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

И только убедившись в корректности решения, имеет смысл обсуждать, насколько быстро оно работает.

Представим, что у нас есть два корректных алгоритма. Оба дают одинаковый результат, но первый выполняет несколько десятков действий, а второй – несколько миллионов.

На маленьких данных разница может быть незаметна: если нужно обработать всего 10 элементов, оба решения закончат работу практически мгновенно. Но если элементов 1 000 000, разница между алгоритмами становится гораздо важнее.

То же самое относится и к памяти: одно решение может хранить большое количество дополнительных данных, а другое – обходиться почти без них.

Поэтому при изучении алгоритмов нас будут интересовать три вопроса:

Готовый код обычно появляется не первым. Сначала есть задача, затем идея, как её решить, из идеи получается алгоритм, и только в конце – запись на конкретном языке:

Разбираться в алгоритмах – значит работать в первую очередь с первыми четырьмя шагами этой цепочки.

До сих пор мы работали с числами, записанными в виде массива:

Но массив – только один из способов организовать данные. Например, элементы можно связать друг с другом, и тогда каждый из них знает, кто идёт следующим:

Данные можно организовать и в виде дерева – тогда у элемента появляются потомки:

А иногда важнее всего связи между объектами – кто с кем соединён:

Все эти варианты хранят одни и те же числа, но организуют их по-разному. Такой способ организации данных называется структурой данных.

От структуры зависит, какие операции выполнять легко, а какие – сложно. Найти элемент по номеру в массиве просто, а в связном списке для этого придётся пройти по ссылкам от самого начала.

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