Сортировка, поиск и интуиция Big-O
Почему одна и та же задача мгновенна на десяти элементах и зависает на десяти миллионах
Главная идея: скорость алгоритма зависит не столько от машины, сколько от того, как растёт его работа при росте входных данных. Нотация Big-O описывает этот рост. Линейный перебор удваивает работу при удвоении данных; двоичный поиск этого почти не замечает. Умение читать рост позволяет заранее, ещё до запуска, предсказать, какой подход останется быстрым на больших объёмах.
К концу вы сможете:
- реализовать линейный поиск и двоичный поиск и сказать, когда каждый применим,
- написать сортировку пузырьком и сортировку вставками и сравнить их со встроенной сортировкой Python,
- читать классы
O(1),O(n),O(n log n)иO(n^2), - использовать
timeit, чтобы превратить теорию в измеренные числа, - выбирать подходящий инструмент, рассуждая о росте, а не наугад.
1. Почему важен именно размер входных данных
Любой код быстр на крошечном списке. Интересно то, что происходит, когда вход растёт до тысяч или миллионов элементов. Мы измеряем алгоритм не в секундах (они зависят от вашего процессора), а в числе базовых шагов, которые он выполняет как функцию от размера входа, обозначаемого n.
Если удвоение n примерно удваивает число шагов, рост линейный. Если удвоение n увеличивает шаги вчетверо, рост квадратичный и накажет вас на масштабе. Big-O оставляет только доминирующее слагаемое и отбрасывает константы, потому что на больших n именно доминирующее слагаемое решает всё.
Если не сказано иначе, мы описываем худший случай: вход, который заставляет сделать максимум работы. Это честное обещание, которое может дать алгоритм.