Алгоритмы

5.1 Что такое алгоритм?

Под алгоритмом понимается точная, пошаговая инструкция решения какой-либо задачи. Это понятие не относится только к компьютерам: и кулинарный рецепт, и указания, как пройти по маршруту, — тоже алгоритм. Точные шаги, точный порядок, точный результат.

А в программировании одну задачу часто можно выполнить несколькими разными алгоритмами. Например, найти какое-то имя в телефонной книге. Можно листать с первой страницы до последней, а можно открыть книгу посередине и определять, в какой она половине. Оба способа дают верный результат, но один намного быстрее.

Именно здесь становится важна эффективность (efficiency): за сколько шагов алгоритм завершает работу. На малых данных разница незаметна, но в списке из миллиона элементов медленный алгоритм может работать часами, а быстрый — за секунды.

5.2 Линейный поиск

Линейный поиск (linear search) — самый простой способ: начиная с начала массива, мы по очереди проверяем каждый элемент, пока не найдём искомое значение или не дойдём до конца. Проход по массиву с помощью цикла из прошлой недели — это именно оно.

Ниже измените искомое число и кнопкой Следующий шаг понаблюдайте за каждой проверкой. Жёлтая ячейка — проверяемый сейчас элемент, зелёная ячейка — найденное место:

В худшем случае (значение в конце или его вообще нет) мы проверяем все элементы. Значит, для 100 элементов может понадобиться 100 шагов, а для миллиона — миллион шагов. Это медленно, но зато он работает и на неотсортированном массиве, вот чем он удобен.

5.3 Двоичный поиск

Если массив отсортирован (упорядочен от меньшего к большему), есть гораздо более умный способ: двоичный поиск (binary search). Идея похожа на телефонную книгу: мы открываем середину. Если искомое значение больше среднего, на левую половину мы вообще не смотрим; если меньше — не смотрим на правую. На каждом шаге оставшийся диапазон сокращается вдвое.

Ниже отсортированный массив. Выберите значение и наблюдайте: светлая ячейка — ещё рассматриваемый диапазон, жёлтая ячейка — середина, зелёная ячейка — найденное место:

Вот в чём магия: массив из 8 элементов двоичный поиск просматривает максимум за 3 шага, потому что каждый раз мы отбрасываем половину (8 → 4 → 2 → 1). А для миллиона элементов хватит всего 20 шагов! Но есть одно условие: массив должен быть заранее отсортирован.

Сделайте прогноз

5.4 Эффективность: Big-O

Чтобы сравнивать скорость алгоритмов, программисты используют обозначение Big-O. Оно показывает не точное время, а то, как растёт число шагов при увеличении объёма данных (n). Самые распространённые:

• O(1) постоянная: каким бы ни был объём, одно и то же число шагов. Самая быстрая
• O(log n) логарифмическая: при удвоении объёма добавляется всего один шаг. Так работает двоичный поиск
• O(n) линейная: равна объёму. Так работает линейный поиск
• O(n^2) квадратичная: квадрат объёма. Так работают простые сортировки, медленно

Ниже выберите n и сравните, сколько шагов требует каждый вид скорости:

5.5 Что такое сортировка и зачем она нужна?

Под сортировкой (sorting) понимается размещение элементов массива в некотором порядке, например от меньшего к большему. Контакты телефона по алфавиту, товары магазина по цене, результаты экзамена по баллам — всё это сортировка.

Сортировка важна ещё по одной причине: она ускоряет другие алгоритмы. Вспомните, двоичный поиск работал только на отсортированном массиве. Значит, отсортировав один раз, потом мы можем искать тысячи раз быстро.

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

5.6 Сортировка пузырьком

Сортировка пузырьком (bubble sort) — самый легко понимаемый способ. Идея: мы сравниваем два соседних элемента, и если левый больше, меняем их местами. Так мы проходим по массиву, затем снова с начала, пока не понадобится ни одной перестановки. На каждом проходе самый большой элемент, словно пузырь, «всплывает» на своё последнее место.

Кнопкой Следующий шаг понаблюдайте за каждым сравнением и перестановкой. Жёлтые столбцы — те, что сравниваются сейчас, оранжевые — те, что меняются местами, зелёные столбцы — нашедшие своё место:

Сортировка пузырьком проста, но медленна: поскольку она снова и снова сравнивает каждую пару, её эффективность O(n^2). То есть для 100 элементов примерно 10 000 операций. Для малых массивов хороша, для больших не годится.

5.7 Сортировка выбором

Сортировка выбором (selection sort) — другая стратегия: каждый раз мы находим наименьший элемент из оставшейся неотсортированной части и ставим его вперёд. На первом проходе находим наименьший во всём массиве и ставим на позицию 0, на втором — наименьший из оставшихся на позицию 1, и так далее.

Наблюдайте ниже: жёлтый столбец — проверяемый сейчас элемент, оранжевый — найденный к этому моменту наименьший кандидат, зелёные столбцы — нашедшие своё место:

Сортировка выбором тоже O(n^2): она тоже для каждого элемента просматривает остальные. Но она делает меньше перестановок (всего одну за проход), поэтому в некоторых случаях практичнее пузырьковой.

5.8 Сравнение алгоритмов

Теперь сравним всё увиденное в одной таблице. Обратите внимание: скорость зависит не только от алгоритма, но и от условия (например, двоичный поиск требует отсортированного массива).

Есть и более быстрые способы сортировки (например, сортировка слиянием, O(n log n)), их мы рассмотрим ниже и в следующих неделях. Пока основной вывод: O(log n) очень быстра, O(n) средняя, а O(n^2) на большом объёме медленна.

5.9 Практика: какой алгоритм выбрать?

Лучшего алгоритма не существует, выбор зависит от ситуации. Вот простые правила:

• Если массив маленький или вы ищете всего один раз: линейного поиска достаточно, он проще
• Если вы ищете в одном массиве много раз: сначала отсортируйте один раз, затем используйте двоичный поиск
• Если данные не отсортированы и их много: выбирайте не простые сортировки, а более быстрый способ (O(n log n))
• Для обучения или небольшой задачи: сортировки пузырьком и выбором отлично подходят, их код короткий

5.10 Глубже advanced

Вы изучили основные алгоритмы. Теперь кратко взглянем ещё на две идеи, которые мы глубже изучим в следующих неделях.

Разделяй и властвуй

Самые быстрые сортировки (например, сортировка слиянием, merge sort) работают иначе: массив делится на две равные части, каждая половина сортируется отдельно, затем две отсортированные половины объединяются. Этот подход даёт скорость O(n log n), что намного лучше O(n^2). Его называют «разделяй и властвуй» (divide and conquer).

Рекурсия

Шаг «отсортируй каждую половину отдельно» выше интересен: функция вызывает сама себя на меньшей части. Это называется рекурсией — вызов функцией самой себя. Это мощное, но тонкое понятие мы полностью изучим на 8-й неделе.

Словарь терминов

5.11 Тест знаний

16 вопросов. Чтобы завершить неделю, ответьте правильно как минимум на 11 из них.