Вход, выход и ограничения
У каждой задачи есть данные, которые мы получаем, и результат, который нужно получить. Дополнительно существуют ограничения: сколько элементов, какого они типа и сколько времени допустимо потратить. Эти ограничения не являются декоративной частью условия. Они помогают выбрать между простым перебором, сортировкой, хеш-таблицей или другой структурой.
Последовательность, условие и повторение
Большинство простых алгоритмов строится из трёх идей: выполнить шаги по порядку, выбрать действие по условию и повторить действие несколько раз. Из этих конструкций создаются гораздо более сложные программы. Полезно тренироваться на задачах, где один и тот же результат можно получить разными способами и сравнить решения.
Структуры данных
Выбор способа хранения влияет на алгоритм. Массив удобен для последовательного доступа, множество — для проверки уникальности, очередь — для обработки в порядке поступления. Не нужно учить структуры как список терминов. Лучше связывать каждую с вопросом: какое действие я хочу выполнять быстро и часто?
Оценка сложности
Два корректных алгоритма могут сильно отличаться по скорости на больших данных. Нотация O описывает, как растёт количество операций вместе с размером входа. Новичку достаточно сначала различать постоянную работу, линейный проход и вложенные переборы. Такая оценка помогает заранее заметить решение, которое станет непрактичным при увеличении входа.
Попробуйте на практике
Придумайте два алгоритма поиска повторяющегося числа в списке.
- Сначала опишите простой вариант со сравнением элементов.
- Затем придумайте решение с дополнительной структурой для хранения уже встреченных значений.
- Запишите шаги каждого алгоритма обычными словами.
- Сравните их по времени и дополнительной памяти.
Как проверить результат. Упражнение выполнено, если оба алгоритма корректны, а вы можете объяснить, почему один требует больше времени, а другой больше памяти.
Частые вопросы
Нужно ли знать математику, чтобы изучать алгоритмы?
Для базового уровня достаточно школьной логики и арифметики. Более сложные области постепенно требуют дополнительной математики.
На каком языке лучше учить алгоритмы?
На том, синтаксис которого уже достаточно знаком, чтобы язык не отвлекал от самой логики решения.
Нужно ли запоминать алгоритмы?
Полезнее понимать идею, условия применения и уметь восстановить решение, чем механически хранить код в памяти.
Самостоятельный разбор темы. Содержание конкретной обучающей программы здесь не представлено.