Чтобы что-то было сделано компьютером, нужно указать ему, как это сделать. Нужно написать программу с пошаговым объяснением: какие задачи компьютер должен выполнить и каким образом. В этом нам помогают алгоритмы.
Алгоритмы — это набор инструкций, используемых компьютерами для решения тех или иных задач, ведущих к достижению конечной цели.
Знание алгоритмов имеет важнейшее значение для создания и разработки эффективных компьютерных программ. В этой статье я хотел бы поделиться своим опытом изучения алгоритмов в университете и рассказать о том, как он помог мне в учебе и карьере.
Первое знакомство
Я начал программировать, когда ещё учился в средней школе. А первые шаги делал, создавая калькуляторы и светофоры на Visual Basic. Позже освоил HTML и Java. В то время я разрабатывал настольные и веб-приложения. Я просто писал хоть какой код, о внутренней логике и не задумывался.
Поступив в университет на специальность компьютерных наук, на втором курсе я начал изучать структуры данных и алгоритмы. Это был обязательный курс, поэтому его должен был пройти каждый.
Из программиста в разработчики
Изучение структур данных и алгоритмов стало поворотным пунктом в моём понимании компьютерного программирования: теперь я думал больше как инженер-разработчик, а не как программист. Почему я так говорю? Приведу несколько примеров.
Пример 1: алгоритмы сортировки
Представьте, что мы делаем приложение для интернет-магазина. Нам надо, чтобы пользователи могли просматривать товары в порядке возрастания цены. Для этого товары нужно отсортировать по цене. Будь я начинающим программистом, добавил бы цены в массив (или список) с записью их индексов и просто вызвал бы встроенный в массив метод sort(). Что на самом деле происходит внутри метода sort()? Когда я раньше делал приложения, я об этом и понятия не имел.
Алгоритмы сортировки — это одна из базовых тем, которую в первую очередь проходят на курсе по изучению структур данных и алгоритмов в университете.
Различают следующие алгоритмы сортировки:
- сортировка вставками;
- сортировка выбором;
- быстрая сортировка;
- сортировка пузырьком;
- сортировка слиянием.
Изучив различные алгоритмы сортировки, я понял, что для каждой задачи нужен свой алгоритм сортировки. Все алгоритмы сортировки различаются по временной сложности, которая зависит от размера данных. Наибольшее значение имеет их время выполнения при разработке приложений, даже если это всего лишь несколько секунд. Кроме того, я узнал о внутренних алгоритмах сортировки (сортировка элементов на месте) и внешних алгоритмах сортировки (требуют дополнительного пространства для хранения элементов во время сортировки). Всё это заставило меня тщательно обдумывать выбор алгоритмов сортировки для каждого конкретного приложения, принимая во внимание ограничения по времени и памяти.
Пример 2: синтаксический анализ математических выражений
При вводе какого-нибудь математического выражения в калькулятор или в ячейку электронной таблицы, например MS Excel, оно автоматически вычисляется, и мы получаем ответ. Вы когда-нибудь задумывались о том, как это выражение высчитывается? А вот нам пришлось разработать программное обеспечение для работы с электронными таблицами и реализовать парсер выражений. Именно тогда я узнал о популярном алгоритме сортировочной станции. В нём используется очередь для хранения значений и стек для хранения операторов. Я узнал о реальных приложениях, в которых применяются такие структуры данных, как очереди и стеки (изучал их на курсе по структурам данных и алгоритмам), и понял лежащую в их основе логику. Меня так и распирала гордость оттого, что удалось самостоятельно реализовать алгоритм сортировочной станции, хотя таких реализаций тогда было уже полным-полно. 😃
Пример 3: списки, множества и словари
Когда нужно сохранить кучу значений, я применяю списки. Раньше я не задумывался, нужно ли соблюдать очерёдность или нужно ли допускать дубли: просто использовал список для всего подряд. Узнав о том, что, помимо списков, существуют ещё словари и множества, я понял, что всё это можно применять в различных сценариях. Так, сделав правильный выбор в той или иной ситуации и отдав предпочтение, скажем словарю, можно фактически ускорить выполнение кода. Например, если надо проверить принадлежность элемента, гораздо быстрее это будет сделать во множестве или словаре (на это требуется константное время), чем при использовании списка (требуется время, пропорциональное длине списка). Кроме того, список допускает наличие дублей, в то время как множество — нет.
Всё это примеры из моего опыта, иллюстрирующие переход от мышления программиста к мышлению инженера-разработчика. Когда я делал выбор в пользу более подходящей структуры данных или более быстрого алгоритма, происходило значительное улучшение производительности моего кода.
С чего начать?
Изучаем концепции программирования
Прежде чем приступать к изучению алгоритмов, я бы порекомендовал освоить такие понятия программирования, как переменные, функции, классы и особенно понятия объектно-ориентированного программирования (ООП). Это будет вашим фундаментом для понимания более продвинутых концепций из области компьютерных наук.
Осваиваем алгоритмы и их принципы работы
Помимо материалов моего курса, я занимался также по учебнику «Алгоритмы: построение и анализ» Томаса Х. Кормена, Чарльза Э. Лейзерсона, Рональда Ривеста и Клиффорда Штайна. Можно начать с самых азов:
- анализа временной и пространственной сложности;
- терминов “O” большое и “o” малое;
- рекурсии;
- базовых структур данных, таких как массивы, матрицы, связные списки, стеки, очереди, деревья и т. д.;
- основных алгоритмов, таких как алгоритмы поиска и сортировки.
Анализ временной и пространственной сложности — это очень важная тема, которую необходимо освоить, чтобы анализировать алгоритмы. Затем можно перейти к более продвинутым алгоритмам, таким как алгоритмы на графах.
Самое важное — чётко понимать, что происходит внутри алгоритма. Раньше я брал простые примеры и применял алгоритм, чтобы посмотреть, что происходит на каждом его шаге. Проработка примеров помогала мне лучше понять, что происходит в алгоритме, причём мне никогда не приходилось эти алгоритмы запоминать. Если меня попросят написать псевдокод для алгоритма, я смогу легко связать его с примером и проработать его, вместо того чтобы запоминать каждый шаг.
Погружаемся в код с головой
На курсе нам предлагалось реализовать различные структуры данных с нуля, используя основные их операции. Например, двоичные деревья поиска (BST) в C++ с операциями вставки, удаления, поиска, обхода с предварительной выборкой, обхода с отложенной выборкой и обхода с порядковой выборкой. Приходилось создавать класс BST и реализовывать все эти операции в виде функций. Предлагалось даже сравнивать время выполнения определённых операций с различными размерами наборов данных. Это был отличный опыт. Я многому научился благодаря этим занятиям и стал лучше разбираться в операциях. Такой учебный процесс с практическими заданиями помог мне лучше понять концепцию алгоритмов.
Можно начать программировать с языков, поддерживающих ООП. Это легко с очень простыми в освоении языками:
- C++
- Java
- Python
Для новичков один из этих языков будет в самый раз.
Ресурсы для обучения
Онлайн-курсы
Можно заниматься дистанционно на:
- Coursera: специализация «Алгоритмы», специализация «Структуры данных и алгоритмы», «Алгоритмы, часть I», «Алгоритмы, часть II».
- MIT Open Courseware: «Введение в алгоритмы».
- Академия Хана: «Алгоритмы».
- Udacity: «Введение в алгоритмы», «Введение в структуры данных и алгоритмы», «Структуры данных и алгоритмы», «Введение в алгоритмы для студентов», «Вычислимость, сложность и алгоритмы».
- edX: «Алгоритмы: дизайн и анализ, часть 1», «Алгоритмы: дизайн и анализ, часть 2», «Алгоритмы и структуры данных», «Алгоритмы: дизайн и техники», «Алгоритмы: дизайн и анализ», «Графовые алгоритмы».
и многие другие платформы. Для лучшего понимания можно попробовать приведённые там упражнения.
Средства интерактивной визуализации алгоритмов
Кроме того, можно попробовать платформы визуализации алгоритмов:
- Визуализация структуры данных.
- Визуализатор алгоритмов.
- VisuAlgo.
- Визуальное отображение алгоритмов сортировки| Toptal.
- Анимированные алгоритмы.
- Визуализации и визуальное отображение алгоритма.
Они доступны в Интернете и понимают пошаговый механизм работы алгоритмов.
Упражнения на закрепление
Освоив азы, можно переходить к практическим занятиям, закрепляя пройденный материал в упражнениях. Вот платформы, на которых собраны очень хорошие задачи самых разных уровней сложности:
Чем больше практики, тем лучше понимание. Закрепление учебного материала в упражнениях — это хороший способ узнать, как изученные теории можно применить в решении задач.
Подводя итоги
Резюмируем статью списком из десяти рекомендаций для тех, кто приступает к изучению алгоритмов:
- Начинайте с изучения основ.
- Сформируйте чёткое понимание того, что происходит в алгоритме.
- Прорабатывайте шаги алгоритма с примерами.
- Обстоятельно разберитесь в анализе сложности.
- Попробуйте самостоятельно реализовывать алгоритмы.
- Записывайте всё важное, чтобы вернуться к этому в будущем.
- Занимайтесь дистанционно на онлайн-курсах платформ для обучения.
- Следите за онлайн-лекциями, опубликованными известными университетами.
- Закрепляйте пройденный материал в упражнениях.
- Если среди упражнений вам попались трудные задачи, не расстраивайтесь. После завершения упражнения можно будет почитать специальную инструкцию и понять, где вы застряли.
Дополнительные материалы для чтения
Если хотите узнать больше о структурах данных и алгоритмах, то можете ознакомиться со следующими статьями:
Заключение
Не забывайте о том, что путь к совершенству — практика!
Надеюсь, для вас эта статья была полезной и познавательной.
Спасибо за внимание.
Читайте также:
- Алгоритмы поиска, которые должен знать каждый специалист по обработке и анализу данных
- Алгоритмы машинного обучения простым языком. Часть 1
- 10 Графовых алгоритмов
Читайте нас в Telegram, VK и Яндекс.Дзен
Перевод статьи Vijini Mallawaarachchi: How to be Good at Algorithms?
