Какими бывают алгоритмы
Несмотря на слово «последовательность», алгоритм не всегда описывает
действия в жестко заданном порядке. Особенно это актуально сейчас, с
распространением асинхронности в программировании. В алгоритмах есть место для
условий, циклов и других нелинейных конструкций.
Линейные. Это самый
простой тип алгоритма: действия идут друг за другом, каждое начинается после
того, как закончится предыдущее. Они не переставляются местами, не повторяются,
выполняются при любых условиях.
Ветвящиеся. В этом
типе алгоритма появляется ветвление: какие-то действия выполняются, только если
верны некоторые условия. Например, если число меньше нуля, то его нужно удалить
из структуры данных. Можно добавлять и вторую ветку: что делать, если условие
неверно — например, число больше нуля или равно ему. Условий может быть
несколько, они могут комбинироваться друг с другом.
Циклические. Такие
алгоритмы выполняются в цикле. Когда какой-то блок действий заканчивается, эти
действия начинаются снова и повторяются некоторое количество раз. Цикл может
включать в себя одно действие или последовательность, а количество повторений
может быть фиксированным или зависеть от условия: например, повторять этот блок
кода, пока в структуре данных не останется пустых ячеек. В некоторых случаях
цикл может быть бесконечным.
Рекурсивные. Рекурсия —
это явление, когда какой-то алгоритм вызывает сам себя, но с другими входными
данными. Это не цикл: данные другие, но «экземпляров» работающих программ
несколько, а не одна. Известный пример рекурсивного алгоритма — расчет чисел
Фибоначчи.
Рекурсия позволяет изящно решать некоторые задачи, но с ней надо быть
осторожнее: такие алгоритмы могут сильно нагружать ресурсы системы и работать
медленнее других.
Вероятностные. Такие
алгоритмы упоминаются реже, но это довольно интересный тип: работа алгоритма
зависит не только от входных данных, но и от случайных величин. К ним,
например, относятся известные алгоритмы Лас-Вегас и Монте-Карло.
Основные и вспомогательные. Это еще один вид классификации. Основной алгоритм решает
непосредственную задачу, вспомогательный решает подзадачу и может
использоваться внутри основного — для этого там просто указываются его название
и входные данные. Пример вспомогательного алгоритма — любая программная
функция.
Графическое изображение алгоритмов
Алгоритмы могут записывать текстом, кодом, псевдокодом или графически — в
виде блок-схем. Это специальные схемы, состоящие из геометрических фигур,
которые описывают те или иные действия. Например, начальная и конечная точка на
схеме — соответственно, начало и конец алгоритма, параллелограмм — ввод или
вывод данных, ромб — условие. Простые действия обозначаются прямоугольниками, а
соединяются фигуры с помощью стрелок — они показывают последовательности и
циклы.
В схемах подписаны конкретные действия, условия, количество повторений
циклов и другие детали. Это позволяет нагляднее воспринимать алгоритмы.
Сложность алгоритма
Понятие «сложность» — одно из ключевых в изучении алгоритмов. Оно означает
не то, насколько трудно понять тот или иной метод, а ресурсы, затраченные на
вычисление. Если сложность высокая, алгоритм будет выполняться медленнее и,
возможно, тратить больше аппаратных ресурсов; такого желательно избегать.
Сложность обычно описывают большой буквой O. После нее в скобках
указывается значение, от которого зависит время выполнения. Это обозначение из
математики, которое описывает поведение разных функций.
Какой бывает сложность. Полностью
разбирать математическую O-нотацию, как ее называют, мы не будем — просто перечислим
основные обозначения сложности в теории алгоритмов.
O(1) означает, что алгоритм выполняется за фиксированное константное
время. Это самые эффективные алгоритмы.
O(n) — это сложность линейных алгоритмов. n здесь и
дальше обозначает размер входных данных: чем больше n, тем дольше
выполняется алгоритм.
O(n²) тоже означает, что чем больше n, тем выше
сложность. Но зависимость тут не линейная, а квадратичная, то есть скорость
возрастает намного быстрее. Это неэффективные алгоритмы, например с вложенными
циклами.
O(log n) — более эффективный алгоритм. Скорость его выполнения
рассчитывается логарифмически, то есть зависит от логарифма n.
O(√n) — алгоритм, скорость которого зависит от квадратного корня
из n. Он менее эффективен, чем логарифмический, но эффективнее
линейного.
Существуют также O(n³), O(nn) и другие малоэффективные алгоритмы с высокими
степенями. Их сложность растет очень быстро, и их лучше не использовать.
Графическое описание сложности. Лучше разобраться в сложности в O-нотации поможет график. Он
показывает, как изменяется время выполнения алгоритма в зависимости от размера
входных данных. Чем более пологую линию дает график, тем эффективнее алгоритм.
O-нотацию используют, чтобы оценить, эффективно ли использовать ту или иную
последовательность действий. Если данные большие или их много, стараются искать
более эффективные алгоритмы, чтобы ускорить работу программы.
Использование алгоритмов в IT
Мы приведем несколько примеров использования разных алгоритмов в отраслях
программирования. На самом деле их намного больше — мы взяли только часть,
чтобы помочь вам понять практическую значимость алгоритмов.
Разработка ПО и сайтов. Алгоритмы
используются для парсинга, то есть «разбора» структур с данными, таких
как JSON. Парсинг — одна из базовых задач, например в вебе.
Также алгоритмы нужны при отрисовке динамических структур, выводе оповещений,
настройке поведения приложения и многом другом.
Работа с данными. Очень
активно алгоритмы применяются при работе с базами данных, файлами, где хранится
информация, структурами вроде массивов или списков. Данных может быть очень
много, и выбор правильного алгоритма позволяет ускорить работу с ними.
Алгоритмы решают задачи сортировки, изменения и удаления нужных элементов,
добавления новых данных. С их помощью наполняют и проходят по таким структурам,
как деревья и графы.
Отдельное значение алгоритмы имеют в Big Data и анализе данных: там они
позволяют обработать огромное количество информации, в том числе сырой, и не
потратить на это слишком много ресурсов.
Поисковые задачи. Алгоритмы
поиска — отдельная сложная отрасль. Их выделяют в отдельную группу, в которой
сейчас десятки разных алгоритмов. Поиск важен в науке о данных, в методах искусственного
интеллекта, в аналитике и многом другом. Самый очевидный пример — поисковые
системы вроде Google или Яндекса. Кстати, подробности об используемых
алгоритмах поисковики обычно держат в секрете.
Машинное обучение. В
машинном обучении и искусственном интеллекте подход к алгоритмам немного
другой. Если обычная программа действует по заданному порядку действий, то
«умная машина» — нейросеть или обученная модель — формирует алгоритм для себя
сама в ходе обучения. Разработчик же описывает модель и обучает ее: задает ей
начальные данные и показывает примеры того, как должен выглядеть конечный
результат. В ходе обучения модель сама продумывает для себя алгоритм достижения
этого результата.
Такие ИИ-алгоритмы могут быть еще мощнее обычных и используются для решения
задач, которые разработчик не в силах разбить на простые действия сознательно.
Например, для распознавания предметов нужно задействовать огромное количество
процессов в нервной системе: человек просто физически не способен описать их
все, чтобы повторить программно.
В ходе создания и обучения модели разработчик тоже может задействовать
алгоритмы. Например, алгоритм распространения ошибки позволяет обучать
нейросети.