ds_fighter 21 ноября 2022

🙌 12 алгоритмов, которые должен знать каждый разработчик: объясняем на гифках

Алгоритмы давно заняли особую нишу как в Computer Science, так и в разработке ПО. Однако какую роль они играют в жизни разработчика и что конкретно из них следует изучить и знать? Об этом вы узнаете из нашей статьи.
🙌 12 алгоритмов, которые должен знать каждый разработчик: объясняем на гифках

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

Так неужели знания в области алгоритмов бесполезны? Конечно, нет. Что по-настоящему важно, так это умение думать алгоритмически. Не только чтобы воспроизводить и изменять стандартные алгоритмы, но и чтобы вам было комфортно использовать код для решения задач, с которыми вы столкнетесь в роли разработчика.

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

Бинарный поиск

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

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

Бинарный поиск. Источник: <a href="https://brilliant.org/wiki/binary-search/" target="_blank" rel="noopener noreferrer nofollow">brilliant.org</a>
Бинарный поиск. Источник: brilliant.org

Сортировки пузырьком, выбором, вставками

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

Сортировки пузырьком. Источник: <a href="https://commons.wikimedia.org/wiki/File:Bubble-sort-example-300px.gif" target="_blank" rel="noopener noreferrer nofollow">Wikipedia</a>
Сортировки пузырьком. Источник: Wikipedia
Сортировка выбором. Источник: <a href="https://codepumpkin.com/selection-sort-algorithms/" target="_blank" rel="noopener noreferrer nofollow">Codepumpkin.com</a>
Сортировка выбором. Источник: Codepumpkin.com
Сортировка вставками. Источник: <a href="https://studiousguy.com/insertion-sort-in-data-structure/" target="_blank" rel="noopener noreferrer nofollow">Studiousguy.com</a>
Сортировка вставками. Источник: Studiousguy.com

Быстрая сортировка и сортировка слиянием

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

Быстрая сортировка. Источник: <a href="https://commons.wikimedia.org/wiki/File:Quicksort-example.gif" target="_blank" rel="noopener noreferrer nofollow">Wikipedia</a>
Быстрая сортировка. Источник: Wikipedia
Сортировка слиянием. Источник: <a href="https://commons.wikimedia.org/wiki/File:Merge-sort-example-300px.gif" target="_blank" rel="noopener noreferrer nofollow">Wikipedia</a>
Сортировка слиянием. Источник: Wikipedia

Кодирование Хаффмена

Кодирование Хаффмена – это основа современного сжатия текстов. Суть его заключается в анализе частотности появления символов в тексте и построения на его основе дерева из этих символов.

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

Кодирование Хаффмена. Источник: <a href="https://commons.wikimedia.org/wiki/File:Huffman_huff_demo.gif" target="_blank" rel="noopener noreferrer nofollow">Wikipedia</a>
Кодирование Хаффмена. Источник: Wikipedia

Поиск в ширину

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

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

Поиск в ширину. Источник: <a href="https://commons.wikimedia.org/wiki/File:Breadth-First-Search-Algorithm.gif" target="_blank" rel="noopener noreferrer nofollow">Wikipedia</a>
Поиск в ширину. Источник: Wikipedia

Поиск в глубину

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

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

Поиск в глубину. Источник: <a href="https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif" target="_blank" rel="noopener noreferrer nofollow">Wikipedia</a>
Поиск в глубину. Источник: Wikipedia

Градиентный спуск

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

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

Градиентный спуск. Источник: <a href="https://commons.wikimedia.org/wiki/File:Gradient_descent.gif" target="_blank" rel="noopener noreferrer nofollow">Wikipedia</a>
Градиентный спуск. Источник: Wikipedia

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

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

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

Алгоритм Дейкстры. Источник: <a href="https://commons.wikimedia.org/wiki/File:Dijkstra_Animation.gif" target="_blank" rel="noopener noreferrer nofollow">Wikipedia</a>
Алгоритм Дейкстры. Источник: Wikipedia

Обмен ключами Диффи-Хеллмана

Обмен ключами Диффи-Хеллмана – это отличное введение в криптографию. Если конкретизировать, то он работает путем объединения открытых и закрытых ключей (которые представляют из себя очень длинные числа) для шифрования информации, передаваемой между двумя различными сторонами.

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

Обмен ключами Диффи-Хеллмана. Источник: <a href="https://gfycat.com/ru/consciousminorhuia-diffie-hellman-key-exchange-university-of-nottingham" target="_blank" rel="noopener noreferrer nofollow">Gfycat</a>
Обмен ключами Диффи-Хеллмана. Источник: Gfycat

Решение практических задач

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

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

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

Так каков итог?

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

***

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

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

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

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

Источники

МЕРОПРИЯТИЯ

Комментарии

ВАКАНСИИ

Добавить вакансию
Go-разработчик
по итогам собеседования

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ