Многие начинающие разработчики ошибочно полагают, что запоминание стандартных алгоритмов важно. Может быть это и так для некоторых собеседований, но это не особенно важно для того, чтобы быть успешным разработчиком.
Так бесполезны ли вещи, которые вы изучаете на алгоритмических уроках? Конечно, нет. Невероятно важна способность мыслить алгоритмически. Не только для того, чтобы воспроизводить и использовать стандартные алгоритмы, но и для того, чтобы вам было удобно использовать код для решения любых новых проблем, с которыми вы столкнетесь как разработчик.
Вот почему мы составили список из 10 алгоритмов, которые начинающие разработчики должны проработать, чтобы привыкнуть к алгоритмическому мышлению.
1. Бинарный поиск
Бинарный поиск — одна из первых вещей, которым учат на любом уроке информатики. Это, пожалуй, самый простой пример того, как небольшая изобретательность может сделать вещи в буквальном смысле экспоненциально более эффективными.
Бинарный поиск состоит из взятия отсортированного массива, многократного его деления на две части и сравнения искомого элемента с каждой половиной до тех пор, пока не будет найдено решение.
2. Сортировка выбором, пузырьковая и вставками
Алгоритмы сортировки — одни из самых фундаментальных инструментов, которые разработчик должен иметь в своем арсенале. Сортировка выбором, пузырьковая и сортировка вставками — одни из первых, с которыми работают новые разработчики. В любом сценарии, когда скорость имеет значение, вы не будете использовать эти алгоритмы, но работа с ними — отличное введение в работу с массивами и манипулирование ими.
3. Быстрая сортировка и сортировка слиянием
Как и в случае № 2, алгоритмы сортировки отлично подходят для работы с массивами, но быстрая сортировка и сортировка слиянием достаточно эффективны, чтобы их можно было использовать в серьезных приложениях. Понять и уметь использовать эти алгоритмы сортировки («понять», а не «запомнить») необходимо для того, чтобы быть серьезным разработчиком.
4. Код Хаффмана
Алгоритм Хаффмана является основой современного сжатия текста. Он работает, учитывая, как часто в тексте появляются разные символы, и организует их в виде дерева на основе этой частоты.
Выделение времени для работы с кодом Хаффмана — отличный способ освоиться с представлением данных и обходом дерева, двумя наиболее важными проблемами, с которыми имеют дело специалисты в области информатики.
5. Поиск в ширину
Опять же, деревья оказываются в основе многих алгоритмов и программного обеспечения, с которыми работают разработчики. Таким образом, понимание базового обхода дерева является главным приоритетом для начинающего разработчика.
Поиск в ширину работает, исследуя дерево уровень за уровнем, пока не будет найден целевой узел. Поскольку алгоритм буквально проходит каждый уровень, он гарантированно находит решение.
6. Поиск в глубину
Продолжая обход дерева, поиск в глубину — это другой основной подход к поиску элемента в дереве. Вместо того, чтобы работать вниз по дереву уровень за уровнем, он исследует ветвь за ветвью.
Предполагая, что у него нет бесконечного количества ветвей, поиск в глубину также всегда будет работать. Реализация этих двух поисковых алгоритмов не особенно сложна, но невероятно важно научиться использовать один из них вместо другого.
7. Градиентный спуск
Сейчас для многих разработчиков градиентный спуск не обязателен. Однако, если вы прикасаетесь к регрессии или машинному обучению, градиентный спуск будет в основе вашей работы.
Градиентный спуск — это метод, оптимизирующий функции с использованием исчислений. В контексте регрессии и машинного обучения это означает поиск определенных значений, которые минимизируют ошибку в вашем алгоритме прогнозирования. Хотя он, безусловно, более математически сложен, чем многие другие алгоритмы, если вы много работаете с данными и прогнозами, понимание того, как работает градиентный спуск, невероятно важно.
8. Алгоритм Дейкстры
Еще одна невероятно важная проблема, с которой работают разработчики, — поиск пути. Графы оказываются невероятно универсальным способом описания всевозможных задач, связанных с сетями различных объектов.
Алгоритм Дейкстры — это способ найти кратчайший путь между двумя узлами в графе. Это основа большей части работы по поиску путей, и она находит применение во всем, от искусственного интеллекта до игрового дизайна.
9. Обмен ключами Диффи-Хеллмана
Протокол Диффи-Хеллмана — отличное введение в то, как работает криптография. Обмен ключами Диффи-Хеллмана работает путем объединения открытых и закрытых ключей (которые фактически являются длинными числами) для шифрования информации при ее передаче между разными сторонами.
Даже если вы не занимаетесь кибербезопасностью, понимание шифрования и безопасного обмена данными невероятно важно для разработки. Кроме того, хотя алгоритм Диффи-Хелмана далеко не лучший, его невероятно легко реализовать, и он достаточно похож на большинство других методов шифрования.
10. Применение на практике
Первые девять алгоритмов дали вам способы решения архетипичных проблем, с которыми вы можете столкнуться как разработчик. Реальность, однако, такова, что как разработчик вы часто будете сталкиваться с алгоритмическими проблемами, которые являются совершенно новыми. Вот почему более важным, чем запоминание любого алгоритма, является практика — развитие способности решать проблемы алгоритмически.
К счастью, нет недостатка в сайтах с задачами для практики программистов. Некоторые из них:
- https://leetcode.com/
- https://projecteuler.net/ (более математический)
- https://www.hackerrank.com/
Это отличная среда для поиска сложных, но решающихся алгоритмических задач и оттачивания навыков.