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

Java JavaScript PHP Python ~10 минут

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

Для чего нужны алгоритмы
- Как применяют алгоритмы
Свойства алгоритмов
Какими бывают алгоритмы
Как записывают алгоритмы
- Псевдокод: как написать алгоритм без языка программирования
- Графическое изображение алгоритмов
Сложность алгоритма
Использование алгоритмов в IT

Для чего нужны алгоритмы

Алгоритм — последовательность действий для решения определенной задачи. Самый простой бытовой пример — рецепт. Чтобы сделать яичницу, понадобятся яйца, соль, масло, нож и сковорода.

Процесс приготовления легко описать пошагово:

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

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

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

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

Как применяют алгоритмы

Задачи на алгоритмы — популярный вопрос на собеседованиях в IT и обязательная часть программы обучения программистов. Знание алгоритмов позволяет разработчикам не изобретать велосипед, а пользоваться оптимальными решениями.

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

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

Зачем учить алгоритмы:

Они помогают решать задачи правильно. Разработчику нужно выбирать оптимальный путь для достижения цели, учитывая все параметры. То есть создать самый эффективный алгоритм. При выборе из готовых решений все равно потребуется понимание того, как это работает изнутри;
Тренируют мозг. Задачи на алгоритмы держат в тонусе интеллект, учат системно мыслить и применять логику даже к бытовым задачам;
Позволяют пройти собеседование. В большинстве крупных компаний проводят алгоритмические собеседования. Зачастую кандидата просят в режиме реального времени реализовать тот или иной алгоритм. Это позволяет понять, как человек анализирует задачи и решает их.

Свойства алгоритмов

У алгоритмов есть обязательные и необязательные свойства.

Обязательные:

Дискретность

Алгоритм всегда можно разделить на шаги, то есть он — делимая структура. Шаги представляют собой действия, которые идут один за другим в определенном порядке.

Детерминированность

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

Необязательные, но часто встречающиеся свойства:

Массовость

Алгоритмы зачастую могут решать задачи вне зависимости от входных данных. То есть их можно экстраполировать на большинство похожих задач. Но есть алгоритмы, которые вообще не зависят от входных данных. Самый популярный пример — базовая программа «Hello world».

Эффективность

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

Какими бывают алгоритмы

Алгоритмы могут иметь разную конструкцию. Расскажем об основных их видах.

Линейные

Это алгоритмы, предполагающие выполнение действий в строго заданном порядке, где одно следует за другим без повторений и пересечений. Таким алгоритмом можно описать простейшие бытовые операции, например, уже упомянутый рецепт яичницы.

Ветвящиеся

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

Для ветвящегося алгоритма необходимо сделать выбор между истиной (true) и ложью (false).

Например, чтобы приготовить ужин, мать посылает ребенка в магазин и дает ему инструкцию: если будет багет, купить его, если нет — взять Бородинский.

Если вместо ребенка представить машину, то процесс покупки будет таким:

Прийти в магазин.
Есть ли на полке багет?
Ответ true — покупает багет и несет его домой.
Ответ false — покупает Бородинский.

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

Циклические

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

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

С помощью цикла можно дать инструкцию по уборке:

Пройдитесь тряпкой по поверхности.
Поверхность грязная?
Если да, пройдитесь по ней снова.
Поверхность грязная?
Если нет, уборка закончена.

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

Рекурсивные

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

Рекурсия — одна из самых сложных тем в алгоритмическом программировании.

Есть несколько популярных типов алгоритмов, которые чаще всего встречаются в реальных задачах:

Сортировка — типовая операция, позволяющая работать с данными. Существуют алгоритмы быстрой сортировки, методом слияния и т.д.;
Поиск — нахождение элемента в большом наборе данных. Для этого используют хеш-таблицы или бинарный поиск;
Поиск с возвратом — общий метод, решающий задачи, в которых нужно провести полный перебор всех возможных вариантов;
Графы — алгоритм для нахождения кратчайшего пути между двумя узлами или для выявления связности;
Рандомизирование — поиск случайного решения. Такие алгоритмы используют в игровой индустрии.

Как записывают алгоритмы

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

Есть более эффективные методики.

Псевдокод: как написать алгоритм без языка программирования

Языков программирования много и у каждого свой синтаксис. При этом большинство алгоритмов универсальны. Чтобы не привязываться к определенному синтаксису, для объяснения сути алгоритма используют псевдокод.

Псевдокод — это неформальный способ записывать инструкции для машины. Он дает возможность передать суть алгоритма. Но не обязывает автора заботиться обо всех закрывающих скобках.

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

Но псевдокод можно написать и на русском языке, используя перевод операторов. Главное, чтобы читателю это было понятно. Никакой унификации у псевдокода нет.

Графическое изображение алгоритмов

Для визуализации алгоритмов используют блок-схемы. Сейчас их рисуют школьники на информатике. А в работе их создают для описания самых разных процессов.

Блок-схемы состоят из геометрических фигур и соединяющих их стрелок. Каждая фигура — шаг, а стрелка — направление.

У блок-схем есть свои стандартные обозначения, которыми стоит пользоваться:

Овал — начало и конец алгоритма.
Прямоугольник — ввод или вывод данных.
Ромб — условие.

Сложность алгоритма

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

Сложность измеряют при помощи Big O. Этот термин оценивает временную сложность алгоритма в наихудшем значении в зависимости от размера входных данных. Он пришел из математики, где используют обозначение «order of» для сравнения функции роста.

Выделяют в основном несколько уровней сложности:

Константная. У таких алгоритмов время выполнения не зависит от размера входных данных;
Логарифмическая. Время растет медленно через увеличение входных данных. Такой сложностью обладает бинарный поиск;
Линейная. Время выполнения пропорционально увеличению размера входных данных. Ею обладает алгоритм, который позволяет найти наибольший или наименьший элемент в неотсортированном массиве;
Квадратическая. Время зависит от квадрата размера входных данных. Такая сложность наблюдается, например, у алгоритмов сортировки вставками;
Кубическая. Время выполнения зависит от размера входных данных в кубе. Она может быть у алгоритмов с тремя вложенными циклами.

Использование алгоритмов в IT

Алгоритмы — одна из основ современной IT-сферы. На них, как на столпах, держится вся современная разработка. Есть несколько популярных алгоритмов, которые подходят для решения распространенных задач.

Сортировка

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

Слияние. В его основе — сравнение элементов при использовании подхода «разделяй и властвуй»;
Быстрая. Это один из самых распространенных алгоритмов, который использует как «разделяй и властвуй», так и принцип in-place;
Пирамидальная. Алгоритм для поиска данных на основе присваивания приоритетов. Используя их, он формируют очередь, которая позволяет уменьшить время поиска.

На основе этих алгоритмов работают системы искусственного интеллекта и анализа данных.

Алгоритм Дейкстры

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

Безопасное хэширование

Это основа современной криптографии и безопасной передачи информации. С его помощью сервер получает входное сообщение, которое преобразуется в 160-битное хэш-значение.

Сейчас есть два основных алгоритма для хэширования MD4 и SHA-1.

Преобразование Фурье

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

RSA-алгоритм

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

Анализ связей

Этот алгоритм позволяет представить график в виде матрицы. Таким образом, для анализа связей нужно оценить относительную важность каждого из объектов в системе.

Сейчас анализ связей применяют поисковые машины для анализа страниц в интернете, для создания «умной» ленты в социальных сетях и т.д.

Алгоритмы используют во многих сферах IT, перечислим самые популярные.

Машинное обучение

Последние несколько лет эта сфера переживает подъем: несколько раз в год выходят релизы нейросетей — обученных программистами моделей. И с каждым днем они могут выполнять все новые и новые задачи.

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

Веб-разработка

При создании сайтов специалисты используют алгоритмы для парсинга. Это автоматический сбор и систематизация информации при помощи небольших программ — скриптов.

Также без алгоритмов невозможно настроить сортировку в каталоге или вывод оповещения. Иногда эти решения «зашиты» во фреймворк, но программисту нужно понимать, как они работают.

Big Data

Алгоритмы — незаменимый инструмент в анализе данных. С их помощью можно эффективно работать с базами данных, списками и массивами. Задача аналитика — подобрать верный алгоритм, который будет удалять, сортировать, изменять и систематизировать элементы.

Поисковые машины

Одна из самых сложных сфер программирования — создание алгоритмов для поисковых систем. Лучшие умы IT-сферы работают над поисковыми роботами Google или Яндекса.