Как хорошо разбираться в алгоритмах?
Как хорошо разбираться в алгоритмах?
Мой опыт изучения алгоритмов и структур данных в качестве бакалавра информатики
Если вы хотите, чтобы компьютер что-то сделал, вы должны объяснить ему, как это сделать. Вы должны написать компьютерную программу, объясняющую шаг за шагом, какие задачи она должна выполнить и как это сделать. Именно здесь в игру вступают алгоритмы.
Алгоритмы – это набор инструкций, используемых компьютерами для решения поставленной задачи с целью достижения конечной цели.
По моему опыту, изучение алгоритмов имеет решающее значение для проектирования и разработки эффективных компьютерных программ. В этой статье я хотел бы поделиться с вами своим опытом изучения алгоритмов в качестве студента бакалавриата и рассказать о том, как он помог мне в моей карьере и научной работе.
Первое знакомство
Я начал программировать, когда учился в средней школе, на Visual Basic, создавая калькуляторы и симуляторы светофоров. Позже я изучил HTML и Java. Тогда я разрабатывал настольные и веб-приложения. Это было просто кодирование, и иногда я понятия не имел о логике, лежащей в основе.
Поступив в университет и выбрав специальность “Информатика и вычислительная техника”, на втором курсе я начал изучать структуры данных и алгоритмы. Это был обязательный курс, и все должны были его пройти.
От программиста к инженеру-программисту
Курс “Структуры данных и алгоритмы” стал поворотным пунктом в моем понимании компьютерного программирования и заставил меня думать скорее как инженер-программист, чем как программист. Почему я так говорю? Позвольте мне привести несколько примеров.
Пример 1: Алгоритмы сортировки
Предположим, что мы создаем приложение для интернет-магазина. Мы хотим, чтобы пользователи просматривали товары в порядке возрастания цены. Для этого нам нужно отсортировать товары по цене. Как начинающий программист, я бы добавил цены в массив (или список) с записью их индексов и просто вызвал встроенный в массив метод sort(). Что на самом деле происходит внутри метода sort()? Я понятия не имел о точных методах, когда создавал приложения.
Алгоритмы сортировки – одна из основных тем, изучаемых вначале курса структур данных и алгоритмов в университете.
Только после изучения различных алгоритмов сортировки я понял, что не каждый алгоритм сортировки подходит для любой задачи. Они имеют разную временную сложность и зависят от размера данных. Самое главное, что время их работы имеет большое значение при разработке приложений, даже если это всего лишь несколько секунд. Кроме того, я узнал об алгоритмах сортировки на месте (сортируют элементы на месте) и алгоритмах сортировки вне места (требуют дополнительного места для хранения элементов при сортировке). Все это заставило меня глубоко задуматься о том, какие алгоритмы сортировки следует использовать для конкретного приложения, учитывая при этом ограничения по времени и памяти.
Пример 2: Разбор математических выражений
Когда мы вводим математическое выражение в калькулятор или в ячейку электронной таблицы, например MS Excel, оно автоматически оценивается и выдает нам ответ. Вы когда-нибудь задумывались, как происходит оценка выражения? Мы должны были разработать программу для работы с электронными таблицами и реализовать синтаксический анализатор выражений. Именно здесь я узнал о популярном алгоритме shunting-yard. Он использует очередь для хранения значений и стек для хранения операторов. Я узнал о реальных применениях структур данных очереди и стека, которые я изучал в курсе “Структуры данных и алгоритмы”, и понял логику, стоящую за этими решениями. Я так гордился собой после того, как самостоятельно реализовал алгоритм “маневровый двор”, несмотря на то, что многие реализации уже были доступны.
Пример 3: Использование списков, множеств и словарей
Всякий раз, когда мне нужно было хранить кучу значений, я использовал список. Тогда мне было все равно, нужно ли сохранять порядок или допускать дубликаты; я просто использовал список для всего. После того как я узнал о списках, наборах и словарях, я понял, что их можно использовать в разных сценариях, и использование одного из них вместо другого действительно ускорит мой код. Например, если я хочу проверить принадлежность значения, это будет намного быстрее при использовании набора или словаря (занимающего постоянное время), чем при использовании списка (занимающего время, пропорциональное длине списка). Более того, список позволяет хранить дубликаты, в то время как набор не допускает дубликатов.
Это несколько примеров из моего опыта, когда я начал менять свое мышление с программиста на инженера-программиста. Я испытал значительное улучшение производительности своего кода, когда перешел на подходящую структуру данных или изменил алгоритм на более быстрый.
Как начать?
Изучить концепции программирования
До изучения алгоритмов в информатике я хорошо понимал концепции программирования, такие как переменные, функции, классы и особенно концепции объектно-ориентированного программирования (ООП). Эти концепции служат фундаментом для понимания более продвинутых концепций в информатике.
Изучение и понимание алгоритмов и их концепций
Помимо материалов курса, я изучал рекомендованный нами учебник “Введение в алгоритмы” Томаса Х. Кормена, Чарльза Е. Лейзерсона, Рональда Ривеста и Клиффорда Стейна. Вы можете начать с основ, таких как
- Анализ временной и пространственной сложности
- нотация Big O
- Рекурсия
- Основные структуры данных, такие как массивы, матрицы, связанные списки, стеки, очереди, деревья и т.д.
- Основные алгоритмы, такие как алгоритмы поиска и сортировки.
Анализ временной и пространственной сложности – это очень важная тема, которую вы должны понять, чтобы анализировать алгоритмы. Затем вы можете перейти к более сложным алгоритмам, таким как алгоритмы графов.
Самое главное, что нужно помнить, – это то, что вы должны четко понимать, что происходит внутри алгоритма. Раньше я брал простые примеры и применял алгоритм, чтобы увидеть, что происходит на каждом шаге. Проработка примеров помогла мне лучше понять, что происходит в алгоритме, и мне никогда не приходилось запоминать алгоритмы. Если меня просят написать псевдокод для алгоритма, я могу легко сослаться на пример и проработать его, вместо того чтобы точно запоминать каждый шаг.
Испачкать руки кодом
Во время нашего курса нам предлагалось реализовать с нуля различные структуры данных с их основными операциями. Я могу вспомнить реализацию двоичных деревьев поиска (BST) на C++ с операциями insert, delete, search, preorder traversal, postorder traversal и inorder traversal. Мы должны были создать класс BST и реализовать все эти операции в виде функций. Нас даже попросили сравнить время выполнения некоторых операций при различных размерах наборов данных. Это был отличный опыт обучения. Я многому научился благодаря этому упражнению и получил хорошее представление об операциях. Такие виды экспериментального обучения помогли мне лучше усвоить концепции алгоритмов.
Вы можете начать кодировать на языках, поддерживающих ООП. Я обнаружил, что следующие языки очень просты для изучения и написания кода.
Если вы новичок, я бы рекомендовал вам начать с одного из этих языков.
Учебные ресурсы
Онлайн-курсы
Вы можете пройти онлайн-курсы на сайте
и многих других платформах. Вы можете попробовать выполнить предложенные упражнения для лучшего понимания.
Интерактивные визуализаторы алгоритмов
Вы можете опробовать платформы визуализации алгоритмов, такие как,
которые доступны онлайн, и понять, как работают алгоритмы шаг за шагом.
Задачи по программированию
После понимания основ вы можете применить полученные знания на практике, попробовав решить задачи по программированию. Следующие платформы предлагают очень хорошие задачи разного уровня сложности.
Чем больше вы будете практиковаться, тем лучше вы будете понимать. Решение задач по программированию – это хороший способ узнать, как можно применить изученные теории для решения проблем.
Подведение итогов
В заключение этой статьи я хотел бы привести 10 советов, основанных на моем опыте изучения алгоритмов.
- Хорошо понимать основы.
- Четко понимайте, что происходит в алгоритме.
- Разбирайте шаги алгоритма на примерах.
- Хорошо понимайте анализ сложности.
- Попробуйте реализовать алгоритмы самостоятельно.
- Записывайте важные моменты, чтобы потом можно было обратиться к ним.
- Проходите онлайн-курсы на обучающих платформах.
- Изучайте онлайн-лекции, публикуемые известными университетами.
- Пробуйте решать задачи по программированию.
- Если вы столкнулись со сложными задачами в задачах по программированию, не отчаивайтесь. Вы можете прочитать их учебники и понять, где вы застряли, после завершения задачи.
Дальнейшее чтение
Если вы хотите прочитать больше о структурах данных и алгоритмах, вы можете ознакомиться со следующими статьями.