Представьте, что вы готовите яичницу. Сначала разбиваете яйцо, затем солите, жарите на сковороде и подаете на стол. Каждое действие — это шаг в последовательности, которая приводит к результату. Примерно так работают алгоритмы: это пошаговые инструкции, которые помогают решать задачи — от простых (вроде приготовления завтрака) до сложных (вроде расчета маршрута ракеты). Алгоритмы окружают нас повсюду: в приложениях на смартфоне, в работе светофоров, даже в музыке, которую вам рекомендует Spotify.
В этой статье мы разберемся, как устроены алгоритмы, "попробуем их на вкус" и узнаем, чем отличаются линейные, ветвящиеся, циклические и рекурсивные алгоритмы. Вы поймете, что алгоритмы — это не страшные формулы из учебников, а логичные помощники, которые делают наш мир удобнее. И да, яичница тут ни при чем... Или при чем?
1. Что такое алгоритм?
Алгори́тм (лат. algorithmi — от имени среднеазиатского математика Аль-Хорезми) — совокупность точно заданных правил решения некоторого класса задач или набор инструкций, описывающих порядок действий исполнителя для решения определённой задачи. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.
2. Свойства алгоритмов
- Дискретность — алгоритм должен представлять процесс решения задачи как упорядоченное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
- Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных» вероятностный алгоритм становится подвидом обычного.
- Понятность — алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд.
- Завершаемость (конечность) — в более узком понимании алгоритма как математической функции, при правильно заданных начальных данных алгоритм должен завершать работу и выдавать результат за определённое число шагов. Дональд Кнут называет процедуру, которая удовлетворяет всем свойствам алгоритма, кроме, возможно, конечности, методом вычисления (англ. computational method). Однако довольно часто определение алгоритма не включает завершаемость за конечное время. В этом случае алгоритм (метод вычисления) определяет частичную функцию. Для вероятностных алгоритмов завершаемость как правило означает, что алгоритм выдаёт результат с вероятностью 1 для любых правильно заданных начальных данных (то есть может в некоторых случаях не завершиться, но вероятность этого должна быть равна 0).
- Массовость (универсальность). Алгоритм должен быть применим к разным наборам начальных данных.
- Результативность — завершение алгоритма определёнными результатами.
3. Виды алгоритмов
3.1 Линейные алгоритмы
Линейный алгоритм — это алгоритм, образуемый командами, которые выполняются однократно и именно в той последовательности, в которой записаны.
Они представляют собой класс алгоритмов, позволяющих решать задачи за линейную сложность O(n), где n – размерность задачи. Например, если дан массив, содержащий n элементов, где 1 ≤ 𝑛 ≤ 105 , то квадратичная сложность алгоритма обработки не позволит выполнить задачу за 1 секунду. Алгоритмы линейной сложности применяются, в частности, для решения однопроходных задач, т.е. задач, которые обрабатывают данные при считывании без их сохранения. К ним, например, относятся алгоритмы поиска минимума (максимума), поиска минимума на отрезке длины k («на окне») в массиве.
3.2 Ветвящиеся алгоритмы
Ветвящийся алгоритм - это алгоритм, в котором содержится блок перехода или условия, который имеет одну входную линию потока и более одной выходной линии.
Решение о том, какой шаг будет следующим, принимается в зависимости от значения переменной. Условий может быть несколько: если одно верно — выполняется одно действие, а если ложно — другое.
Пример: простой алгоритм, который определяет тип числа:
- Введите число и сохраните его в переменной x.
- Если x больше 0, то выведите «Число положительное».
- Иначе, если x меньше 0, то выведите «Число отрицательное».
- Иначе выведите «Число равно нулю».
В программировании используют ветвящийся алгоритм, когда применяют условные операторы, например if-elif-else в языке Python.
3.3 Циклические алгоритмы
Циклический алгоритм – это алгоритм, содержащий один или несколько циклов. Возьмем для примера задачу: найти сумму некоторого количества чисел, задаваемых пользователем. Исходными данными в этом случае являются переменная N - количество чисел и сами эти числа. Значение очередного числа обозначим переменной x.
Различают три типа циклических алгоритмов:
- Цикл с предусловием. Реализует циклический алгоритм с использованием определённого условия, истинность которого проверяется перед каждой итерацией цикла. Выполнение цикла прекращается, когда условие становится ложным.
- Цикл с постусловием. Это алгоритм циклической структуры, в котором проверка условия продолжения осуществляется после выполнения тела цикла. Тело цикла с постусловием всегда выполняется как минимум один раз, независимо от истинности или ложности условия.
- Цикл с заданным числом повторений. Этот вид цикла вместо логического условия выполнения использует параметр (счётчик) — специальную переменную, которая на каждом шаге цикла получает очередное значение из определённого диапазона. Цикл повторяется до тех пор, пока не будут перебраны все элементы диапазона.
Примеры циклических алгоритмов: перевод текста с иностранного языка (прочитать первое предложение, перевести, записать и т.д.) и построение графика функции по точкам (взять первый аргумент, вычислить значение функции, построить точку и т.д.).
3.4 Рекурсивные алгоритмы
Рекурсия – это определение объекта через обращение к самому себе.
Рекурсивные алгоритмы - это подход, при котором задача решается путем разделения ее на меньшие подзадачи того же типа. То есть, для решения задачи мы вызываем функцию, которая в своем теле снова вызывает сама себя.
Прямое обращение функции к самой себе предполагает, что в теле функции содержится вызов этой же функции, но с другим набором фактических параметров. Такой способ организации работы называется прямой рекурсией. Например, чтобы найти сумму первых n натуральных чисел, надо сумму первых (n-1) чисел сложить с числом n, то есть имеет место зависимость: Sn=Sn-1+n. Вычисление происходит с помощью аналогичных рассуждений. Такая цепочка взаимных обращений в конечном итоге сведется к вычислению суммы одного первого элемента, которая равна самому элементу.
При косвенном обращении функция содержит вызовы других функций из своего тела. При этом одна или несколько из вызываемых функций на определенном этапе обращаются к исходной функции с измененным набором входных параметров. Такая организация обращений называется косвенной рекурсией. Например, поиск максимального элемента в массиве размера n можно осуществлять как поиск максимума из двух чисел: одно их них – это последний элемент массива, а другое является максимальным элементом в массиве размера (n-1). Для нахождения максимального элемента массива размера (n-1) применяются аналогичные рассуждения. В итоге решение сводится к поиску максимального из первых двух элементов массива.
Рекурсивный метод в программировании предполагает разработку решения задачи, основываясь на свойствах рекурсивности отдельных объектов или закономерностей. При этом исходная задача сводится к решению аналогичных подзадач, которые являются более простыми и отличаются другим набором параметров.
Заключение
Если представить, что мир программирования — это кухня, то алгоритмы — рецепты, которые превращают сырые ингредиенты в шедевры. Мы разобрали, как работают линейные алгоритмы (шаг за шагом, без отклонений), ветвящиеся (выбор пути, как на развилке дорог), циклические (повторение действий, как замес теста) и рекурсивные (когда задача вызывает саму себя, как матрешка).
Но это лишь начало. Алгоритмы — основа искусственного интеллекта, шифрования данных, анализа больших массивов информации. Они помогают находить любовь в Tinder, строить маршруты в Google Maps и даже предсказывать погоду. Чем лучше мы их понимаем, тем проще нам "договориться" с технологиями, которые правят миром. А если захотите глубже погрузиться в тему — перед вами открывается целая вселенная. Кто знает, может, ваш будущий алгоритм изменит чью-то жизнь?