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

Что такое алгоритмы и какими они бывают

Ты можешь разрабатывать микросервисы и знать все уровни модели OSI, но какой ты программист, если не можешь объяснить ребёнку, что такое алгоритм?

Иллюстрация: Катя Павловская для Skillbox Media

Антон Сёмин

Пишет об истории IT, разработке и советской кибернетике. Знает Python, JavaScript и немного C++, но предпочитает писать на русском.

Август Вилакия

Ведущий бэкенд-разработчик мобильного приложения «Альфа-Банка».

Иногда совсем простые вопросы о профессии вводят в ступор даже опытных специалистов. Примерно так происходит, когда у разработчика с 5–10-летним стажем спрашивают: «Что такое алгоритм?»

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

• Что такое алгоритмы
• Для чего их используют
• Какие у них есть свойства
• Что такое псевдокод
• Что такое блок-схемы и как их рисовать
• Примеры линейных, ветвящихся, циклических и рекурсивных алгоритмов и блок-схем

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

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

Слово «алгоритм» произошло от имени персидского математика Абу Абдуллаха аль-Хорезми. В своём труде «Китаб аль-джебр валь-мукабала» учёный впервые дал описание десятичной системы счисления. А наука алгебра получила своё название в честь его книги.

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

1. Устанавливаем капсулу.

2. Проверяем уровень воды в специальном отсеке.

3. Если воды недостаточно — доливаем.

4. Ставим чашку под кран кофемашины.

5. Запускаем кофемашину.

6. Выключаем кофемашину, когда чашка наполнилась.

7. Достаём кружку.

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

С компьютерами намного сложнее. Им неизвестно, что значит «установить капсулу», «долить воду», «запустить кофемашину» и так далее. Чтобы запрограммировать робота-баристу под определённую модель бытовой техники, алгоритм придётся расписать более детально:

1. Возьми штепсельную вилку шнура питания кофемашины.

2. Вставь штепсельную вилку в розетку.

3. Проверь, есть ли вода в отсеке для воды.

4. Если воды недостаточно:

4.1. Подними крышку отсека.

4.2. Возьми кувшин с водой.

4.3. Лей воду из кувшина в отсек, пока он не заполнится.

4.4. Закрой крышку отсека.

4.5. Поставь кувшин с водой на стол.

5. Открой крышку кофемашины.

6. Возьми из коробки капсулу с кофе.

7. Вставь капсулу в отсек для капсулы.

8. Закрой крышку кофемашины.

9. Поверни рычаг кофемашины вправо.

10. Когда чашка наполнится, поверни рычаг кофемашины влево.

11. Возьми кружку.

12. Принеси кружку хозяину.

Конечно, если мы собираем робота с нуля, то даже такой детализации будет недостаточно. Каждую процедуру ещё нужно будет реализовать на языке программирования (например, на C++ или Python), что само по себе — нетривиальная задача. Тем не менее описание стало более точным и формальным.

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

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

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

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

Не нужно изобретать велосипеды

Представьте, что оформляете загранпаспорт. Если будете всё делать сами и без инструкции, около 40 минут потратите только на выяснение необходимых справок и порядка оформления. Куда проще воспользоваться «Госуслугами», потому что алгоритм там уже составлен — делаете, что вам говорят, и ждёте результат. А ещё проще — обратиться к посреднику, который подготовит все справки и оформит паспорт за неделю.

Это очень бытовой пример, но программирование примерно так и работает. Разработчики изучают алгоритмы, чтобы писать быстрый и эффективный код, — распознают типовую задачу и подбирают для неё оптимальный алгоритм.

Допустим, нужно отсортировать в порядке возрастания числа в списке из 1000 элементов. Можно пройтись по списку 1000 раз: на каждой итерации находить наименьшее число и переставлять его в начало списка. В этом случае общее количество шагов будет равно 1 000 000 — современный компьютер справится с этим за секунду.

А если нужно упорядочить массив из 10 000 000 элементов? Тогда компьютеру придётся выполнить 10 14 шагов, что потребует гораздо больше времени. Надо оптимизировать!

Разработчик, не сведущий в computer science, начнёт ломать голову над более эффективным решением. А опытный специалист применит алгоритм быстрой сортировки, который в среднем случае даст «время» 16 × 10 7 шагов.

Знатоки скажут, что ещё проще было бы воспользоваться библиотечной функцией сортировки (например, sorted() в Python). Тем не менее даже встроенные алгоритмы бывают недостаточно эффективными и разработчикам приходится писать собственные функции для сортировки. Но это уже совсем другая история ��

Алгоритмы позволяют решать «нерешаемые» задачи

Теперь представьте: вы живёте в XX веке где-нибудь в США и зарабатываете тем, что ездите по городам и продаёте мультимиксеры. Чтобы сэкономить время и деньги, вам нужно придумать кратчайший маршрут, который позволит заехать в каждый город хотя бы один раз и вернуться обратно.

Это знаменитая задача коммивояжёра , для которой практически невозможно подобрать лучшее решение. Простой перебор здесь не поможет. Уже при 10 городах количество возможных маршрутов будет равно 3,6 млн, а при 26 — даже самым мощным компьютерам понадобится несколько миллиардов лет, чтобы перебрать все варианты.

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

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

Информатик и автор классических учебников по программированию Дональд Кнут выделял следующие свойства алгоритмов:

• конечность,
• определённость,
• наличие ввода,
• наличие вывода, или результативность,
• универсальность,
• эффективность.

Рассмотрим каждое подробно.

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

Определённость. Исполнитель (компьютер, операционная система) должен однозначно и верно интерпретировать каждый шаг алгоритма.

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

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

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

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

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

Представьте, что вы изучили какой-нибудь язык программирования, например Go, и устроились бэкенд-разработчиком в IT-компанию. В вашей команде, помимо бэкендеров, есть фронтенд-разработчики, которые пишут код на JavaScript.

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

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

У псевдокода нет общепринятых стандартов, и авторы используют собственные оригинальные нотации. Хотя часто они заимствуют названия операций из Python, Pascal и Java. Например, код ниже напоминает программу на Python:

Никак не обозначается
или обозначается как начало функции:

Операторы ввода и вывода:

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

Знание алгоритмов и тесно связанной с ними организации структуры данных необходимо для серьезной работы в любой отрасли информатики:

1. Протоколы маршрутизации в коммуникационных сетях используют классические алгоритмы поиска кратчайшего пути.
2. Шифрование с открытым ключом опирается на эффективные теоретико-числовые алгоритмы.
3. Компьютерная графика задействует вычислительные примитивы, которые предоставляют геометрические алгоритмы.
4. Индексация в базах данных опирается на структуры данных сбалансированных деревьев поиска.
5. Вычислительная биология использует алгоритмы динамического программирования для измерения сходства геномов.

И так можно продолжать бесконечно.

Что дает знание алгоритмов рядовому разработчику

Освоение алгоритмов требует времени и усилий, но при этом дает несколько серьезных преимуществ:

• Повышение эффективности. Существуют максимально быстрые алгоритмы для обработки данных и эффективные структуры для их организации. Такие паттерны избавляют от необходимости изобретать велосипед при решении типовых задач, позволяют прогнозировать производительность ПО и служат основой для разработки новых нетривиальных решений.
• Развитие аналитических способностей и алгоритмического мышления. Изучение и реализация алгоритмов улучшают не только навыки программирования: привычка разбивать сложные задачи на логически связанные шаги, необходимые для их эффективного решения, пригодится везде – от планирования отпуска до разработки инвестиционной стратегии.
• Успехи в спортивном программировании. Знание алгоритмов необходимо для успешного решения задач в контестах: как правило, из любого олимпиадного задания торчат уши какого-нибудь алгоритма. Вот всего лишь один пример: известная задача «Поле чудес» (Periodic Strings в англоязычном варианте) элементарно решается с помощью алгоритма Кнута-Морриса-Пратта . Стоит заметить, что олимпиадные задачи часто предлагают кандидатам на техническом собеседовании.
• Успешное прохождение собеседований. Чем сложнее задачи, которые предстоит решать разработчикам компании, тем выше вероятность, что значительная часть вопросов будет посвящена алгоритмам и структурам данных. Работодатели отдают предпочтение кандидатам, которые способны найти самое эффективное и эргономичное решение проблемы.
• Знакомство с величайшими достижениями информатики. Изучение алгоритмов и структуры данных похоже на просмотр дайджеста, состоящего из суперхитов информатики за последние 70 лет. В следующий раз, когда коллега пришлет мем про Дейкстру и его путь к подруге, будешь знать, в каком месте надо смеяться.

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

• углубишься в теорию структур данных;
• научишься решать сложные алгоритмические задачи;
• научишься применять алгоритмы и структуры данных при разработке программ.

С чего начать изучение алгоритмов

Существует множество алгоритмов и немало структур данных . Некоторые из них можно назвать универсальными или общими, другие – узкоспециальными, предназначенными для решения специфических задач: очевидно, что в вычислительной геометрии и в биоинформатике проблемы будут разными. Без какой-либо базы (в виде университетского курса или опыта участия в олимпиадах по программированию) разобраться во всем этом довольно сложно. В этом случае важно начать с азов и базовых концепций, к которым относятся:

1. Асимптотический анализ сложности алгоритмов. Лучший, средний и худший случаи. «O» большое и «o» малое. Очень часто на собеседованиях предлагают оценить сложность алгоритма или обосновать выбор в пользу определенного решения.
2. Линейные структуры данных – массивы, стеки, связанные списки, хэш-таблицы и очереди.
3. Нелинейные структуры данных – деревья, графы, множества.
4. Рекурсия. Значительная часть алгоритмов использует рекурсию; она неразрывно связана с рекурсивно определяемыми структурами данных – деревьями, – и восходящим / нисходящим динамическим программированием.
5. Концепция «разделяй и властвуй» и алгоритмы, основанные на ней – бинарный поиск, сортировка слиянием, быстрая сортировка, сортировка подсчетом, умножение Карацубы, субкубический алгоритм Штрассена, задача о паре ближайших точек. Такие алгоритмы разбивают исходную задачу на более мелкие подзадачи, рекурсивно решают их, а затем объединяют решения подзадач в решение исходной задачи.

После знакомства с азами пора переходить к темам, которые всплывают на большинстве собеседований: поиск и сортировка, жадные алгоритмы, графы (поиск в ширину и в глубину), динамическое программирование. Абсолютный минимум, который необходим для подготовки к техническому собеседованию, доступно и интересно изложен в книге Томаса Х. Кормена «Алгоритмы. Вводный курс». Исчерпывающий вариант – четырехтомник Тима Рафгардена «Совершенный алгоритм»:

• в первой книге рассматриваются азы и базовые концепции;
• во второй – графовые алгоритмы и структуры данных;
• в третьей – жадные алгоритмы и динамическое программирование;
• в четвертой – алгоритмы для NP трудных задач.

Материалы четырехтомника основаны на лекциях, которые Рафгарден читал в Стэнфордском университете и на онлайн-курсах, которые он ведет сейчас. Книги написаны вполне доступным языком и содержат множество практических заданий и тестов с решениями.

Алгоритмическая секция

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

• Кандидатам предлагают решить 5-6 задач разной степени сложности. На задачу можно потратить 15-45 минут – это очень мало. Поэтому с первого дня изучения алгоритмов нужно привыкать решать задачи – не только правильно, но и максимально быстро.
• Часто решение приходится писать от руки – на листе бумаги или на доске. Так интервьюеру проще оценить, насколько последовательно и структурированно складывается решение в голове кандидата – чем меньше зачеркиваний и стираний, тем лучше.
• При решении задач в IDE действуют лимиты по времени и памяти, как и в контестах спортивного программирования. Чтобы уложиться в лимиты, нужно учитывать не только быстродействие выбранного алгоритма, но и мелочи вроде небрежного считывания всех данных из огромного файла целиком (вместо одной нужной строчки).

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

Мне сложно разобраться самостоятельно, что делать?

Алгоритмы и структуры данных действительно непростая тема для самостоятельного изучения: не у кого спросить и что-то уточнить. Поэтому мы запустили курс «Алгоритмы и структуры данных», на котором в формате еженедельных вебинаров вы:

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

Курс подходит как junior, так и middle-разработчикам.

Алгоритм

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

Освойте профессию «Data Scientist»

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

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

Науки о данных

Онлайн-магистратура совместно с МФТИ. Погрузитесь в мир Data Science и постройте карьеру в Big Data, Artificial Intelligence или Machine Learning. Получите опыт на реальных проектах и выйдите на новый уровень в профессии и карьере.

Кто пользуется алгоритмами

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

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

Читайте также Востребованные IT-профессии 2023 года: на кого учиться онлайн

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

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

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

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

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

Алгоритмизация

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

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

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

Основные свойства алгоритмов

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

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

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

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

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

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

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

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

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

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

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

Рекурсивные. Рекурсия — это явление, когда какой-то алгоритм вызывает сам себя, но с другими входными данными. Это не цикл: данные другие, но «экземпляров» работающих программ несколько, а не одна. Известный пример рекурсивного алгоритма — расчет чисел Фибоначчи.

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

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

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

Станьте дата-сайентистом и решайте амбициозные задачи с помощью нейросетей

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

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

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

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

Понятие «сложность» — одно из ключевых в изучении алгоритмов. Оно означает не то, насколько трудно понять тот или иной метод, а ресурсы, затраченные на вычисление. Если сложность высокая, алгоритм будет выполняться медленнее и, возможно, тратить больше аппаратных ресурсов; такого желательно избегать.

Сложность обычно описывают большой буквой 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 или Яндекса. Кстати, подробности об используемых алгоритмах поисковики обычно держат в секрете.

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

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

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

Data Scientist

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

Что такое и зачем нужны алгоритмы

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

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

Алгоритм — это набор инструкций для решения какой-то задачи. Всё, что мы делаем: готовим утром кофе, идём на работу, пишем код — это исполнение определённых алгоритмов.

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

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

�� Изучите алгоритмы

Понимание алгоритмов и структур данных поможет писать более эффективный код, правильно выстраивать архитектуру проекта и отдельных модулей.

Востребованы ли алгоритмы на рынке фронтенд-разработки?

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

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

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

• Лишь 2% вакансий с опытом до года требуют знания алгоритмов и структур данных.
• В вакансиях для разработчиков с опытом до шести лет этот навык упоминается в 10% случаев.
• Почти каждая третья вакансия для фронтендеров с опытом более 6 лет содержит этот навык в требованиях к соискателю.

Какие задачи решают с помощью алгоритмов?

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

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

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

Разберём подробнее некоторые типовые задачи, в которых используют алгоритмы.

Сортировка данных

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

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

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

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

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

А затем обновляем связи в списке:

Quicksort — одна из самых быстрых сортировок для использования на больших объёмах данных.

Как она работает: сначала мы выбираем в массиве любой «опорный» элемент. Затем сравниваем каждый из элементов с опорным. По результатам сравнений переставляем элементы в массиве так, чтобы слева от опорного были все элементы меньше него, а справа — больше или равны. После этого запускаем этот же алгоритм рекурсивно на левую и правую части массива, пока не придём к массиву из одного элемента.

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

Теперь берём часть слева и выбираем новый опорный элемент — 3. Затем вновь перемещаем элементы меньше слева от него, а элементы больше — справа. Делаем так, пока полностью не отсортируем левую часть:

Когда закончим, повторим всё то же самое с правой частью:

function quickSort(array, left, right) < left = left ?? 0; right = right ?? array.length - 1; const pivotIndex = partition(array, left, right); logIteration(array, array[pivotIndex], left, right); if (left < pivotIndex - 1) < quickSort(array, left, pivotIndex - 1); >if (pivotIndex < right) < quickSort(array, pivotIndex, right); >return array; > function random(min, max) < const interval = max - min; const shift = min; return Math.round(Math.random() * interval + shift); >function partition(array, left, right) < const pivot = array[random(left, right)]; while (left < right) < while (array[left] < pivot) < left++; >while (array[right] > pivot) < right--; >if (left > return left; > 

Есть множество других видов сортировок. Какой из них использовать — зависит от конкретной задачи.

Поиск в массиве

Найти что-то в массиве — довольно распространённая задача. Это может быть поиск целого объекта по его признаку. Например, когда нам нужно найти объект банковской карточки по id. Или это может быть проверка на вхождение. К примеру, мы можем узнать, разрешено ли показывать определённый контент пользователю. Для этого достаточно проверить его права в массиве прав, разрешающих просмотр.

Линейный поиск — самый распространённый, хотя и медленный, способ поиска в массивах и других коллекциях. Это довольно простой алгоритм, он перебирает все элементы до тех пор, пока не встретит нужный или не дойдёт до конца массива.

Как он работает: к примеру, мы хотим проверить, есть ли слово ‘скрипт’ в массиве [‘веб’, ‘деплой’, ‘сервер’] . Сначала мы посмотрим на ‘веб’ и сравним его с искомым словом. Они не равны, поэтому двигаемся дальше — к слову ‘деплой’ . С ним и ‘сервер’ ситуация такая же: сравнение их со ‘скрипт’ -ом вернёт false . А затем мы придём в конец массива. Это значит, искомого элемента в нём нет.

Проверка на вхождение слова с помощью include :

const words = ['веб', 'деплой', 'сервер']; function checkIfInclude(word) < return words.includes(word); >checkIfInclude('скрипт'); // false 

Если бы мы искали в массиве слово веб , то нашли бы его при сравнении с первым элементом массива и на этом закончили поиск:

Бинарный поиск — поиск, который можно вызывать только на отсортированных массивах данных. Он работает по методу indexOf : принимает элемент, который нужно найти в массиве, и возвращает либо его позицию, либо -1 , либо null .

Бинарный поиск быстрее линейного за счёт того, что он не перебирает каждый элемент. Вместо этого он делит массив пополам и проверяет, в какой части, справа или слева, должен находиться искомый элемент. После этого он делит остаток ещё раз пополам — и так далее, пока не найдёт этот элемент:

Бинарный поиск удобен для работы с большими отсортированными массивами. Представьте, что вам нужно найти пользователя в базе данных из миллиона человек. Если перебирать каждый элемент последовательно, вы потратите немало времени. Гораздо быстрее и проще сузить поиск, отбросив сразу половину элементов.

Простой пример бинарного поиска:

function binarySearch(numbers, target) < let left = 0; let right = numbers.length - 1; while (left if (numbers[center] > target) < right = center - 1; >else < left = center + 1; >> return null; > 

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

Оптимизация кода

В своей работе мы так или иначе работаем с DOM-деревом. Подбор правильных алгоритмов для работы с деревьями помогает ускорить работу страницы при обработке больших фрагментов дерева.

Переобходить DOM-дерево можно разными способами. Самый простой — поиск в ширину. Он хорошо подходит для поиска, если искомый элемент лежит «сверху» и дерево довольно широкое.

Особенность поиска в ширину в том, что мы сначала просматриваем все элементы на одном уровне вложенности, затем переходим на следующий — и так далее, пока не обойдём всё:

const root = document.body; const resultElement = document.getElementById('result'); function traverse(node) < const result = []; const queue = []; queue.push(node); while(queue.length) < const currentNode = queue.shift(); result.push(currentNode.localName); queue.push(. currentNode.children); >resultElement.innerHTML = result.join(' -> '); > traverse(root); 

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

const root = document.body; const resultElement = document.getElementById('result'); function traverse(node) < const result = []; function recursive(node) < result.push(node.localName); for (const child of node.children) < recursive(child); >> recursive(node); resultElement.innerHTML = result.join(' -> '); > traverse(root); 

Отрисовка динамических списков и парсинг

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

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

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

С помощью рекурсии можно быстро перевести его в такой:

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

Всё, что для этого нужно сделать — переобойти DOM, рекурсивно вызывая парсинг.

Добавление данных в очередь

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

Такие задачи очень просто реализуется очередью — структурой данных, «мимикрирующей» под очередь из реальной жизни, когда элементы попадают в конец массива-очереди и достаются из её начала.

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

Вывод

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

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

Один из самых простых способов начать изучение алгоритмов — книги. Начать можно с «Грокаем алгоритмы», в ней Адитья Бхаргава простыми словами пишет о популярных концептах алгоритмостроения, хотя и не всегда применимых к фронтенду. А тем, кто не боится сложного академического языка, советуем прочитать книгу Дональда Кнута «Искусство программирования» о важнейших и базовых алгоритмах, которые мы используем. Можно сказать, что это своего рода «Библия» алгоритмов.

Больше материалов

• Почему разработчики выбирают Vue
• Паттерны проектирования
• Что такое CMS и как под них верстать

«Доктайп» — журнал о фронтенде. Читайте, слушайте и учитесь с нами.