Много алгоритмов для одной задачи
Алгоритм это набор точных шагов для решения задачи. Большинство задач можно решить не одним алгоритмом. Например, чтобы найти имя в списке, можно проверить каждое имя или (если список упорядочен) всё время делить его пополам.
Оба способа дают верный ответ. Разница в эффективности: сколько работы и памяти нужно каждому. Хороший программист выбирает алгоритм, который остаётся быстрым, когда данных становится много.
Сравнение алгоритмов по времени работы
Измерять секундомером нечестно: быстрый компьютер делает медленный алгоритм похожим на хороший. Поэтому мы считаем простые шаги (сравнения, обмены, сложения) как функцию от размера входных данных n.
Лучший, средний и худший случай
Лучший случай это самые удачные данные (13 лежит в первой коробке: 1 шаг). Худший случай это самые неудачные (13 нет: n шагов). Обычно называют худший случай, потому что это гарантия: алгоритм никогда не будет медленнее.
Временная и пространственная сложность
Временная сложность показывает, как растёт число шагов с ростом n. Пространственная сложность показывает, как растёт дополнительная память с ростом n. Сортировка слиянием быстрая, но требует дополнительной памяти; пузырьковой почти не нужна дополнительная память, но она медленная.
Нотация Big O
Big O описывает скорость роста, не обращая внимания на мелкие детали. Мы оставляем только самое большое слагаемое и отбрасываем постоянные числа: 3n² + 5n + 2 превращается в O(n²), потому что при большом n часть n² это почти всё.
| Big O | Название | n = 16 | n = 1000 | Пример |
|---|---|---|---|---|
| O(1) | константная | 1 | 1 | прочитать элемент 5 массива |
| O(log n) | логарифмическая | 4 | около 10 | бинарный поиск |
| O(n) | линейная | 16 | 1000 | линейный поиск, поиск наибольшего |
| O(n log n) | n log n | 64 | около 10 000 | сортировка слиянием |
| O(n²) | квадратичная | 256 | 1 000 000 | пузырьковая сортировка, вложенные циклы |
Быстрое правило для кода: один цикл по n элементам это O(n); цикл внутри цикла это O(n²); деление задачи пополам на каждом шаге это O(log n).
Эффективность линейного и бинарного поиска
Линейный поиск проверяет элементы по одному. Худший случай: n сравнений, то есть O(n). Он работает с любым списком, упорядоченным или нет.
Бинарному поиску нужен упорядоченный список. Смотрим на середину; если она слишком большая, отбрасываем правую половину, иначе левую. Каждый шаг делит список пополам, поэтому в худшем случае нужно около log₂ n + 1 сравнений: O(log n). Для 1 000 000 элементов это около 20 шагов вместо 1 000 000.
Эффективность алгоритмов сортировки
Пузырьковая сортировка, сортировка вставками и выбором используют цикл внутри цикла, поэтому им нужно около n²/2 сравнений: O(n²). Сортировка вставками в лучшем случае (список уже упорядочен) работает за O(n).
Сортировка слиянием делит список пополам примерно log₂ n раз и на каждом уровне делает около n работы: O(n log n). Ей нужно O(n) дополнительной памяти.
Бинарному поиску нужен упорядоченный список. Если искать только один раз, сначала сортировать (n log n) дороже, чем один линейный поиск (n). Если искать много раз, один раз отсортировать выгодно.
Предусловия, постусловия и ловушки рекурсии
Предусловие это то, что должно быть верно до начала алгоритма (для бинарного поиска: список упорядочен). Постусловие это то, что гарантировано после окончания (для сортировки: каждый элемент меньше или равен следующему). Если записать их, алгоритм проще проверять и доказывать.
Рекурсия означает, что функция вызывает сама себя для меньшей задачи. Частые ошибки:
- Нет базового случая или он никогда не достигается: вызовы не прекращаются (переполнение стека).
- Задача не уменьшается при каждом вызове.
- Повторение одной и той же работы: простая рекурсивная функция Фибоначчи снова и снова вызывает fib(3), поэтому растёт как O(2ⁿ). Если запоминать ответы (мемоизация), получится O(n).
- Очень глубокая рекурсия занимает много памяти: один кадр стека на каждый вызов.
Попробуйте: гонка двух поисков
Напишите числа от 1 до 32 на бумажках и разложите их по порядку лицом вниз. Пусть друг загадает число. Сначала ищите по одной бумажке и считайте, сколько перевернули. Потом ищите, всегда переворачивая среднюю бумажку. Повторите 5 раз. Какому способу ни разу не понадобилось больше 6 переворотов? Проверьте ползунком в последнем 3D-шаге (n = 32: log₂ 32 = 5).
Главные формулы и определения
- Линейный поиск: худший случай n сравнений → O(n)
- Бинарный поиск: худший случай около log₂ n + 1 сравнений → O(log n)
- Сортировка пузырьком / вставками / выбором: около n(n − 1)/2 сравнений → O(n²)
- Сортировка слиянием: около n log₂ n сравнений → O(n log n)
- Правило Big O: оставляем самое большое слагаемое, отбрасываем константы (5n² + 3n → O(n²))
- Удвоение n: O(1) без изменений, O(log n) +1, O(n) ×2, O(n²) ×4
Разобранные примеры
1. В списке 50 имён. Сколько сравнений нужно линейному поиску в лучшем и в худшем случае?
Лучший случай: имя первое → 1 сравнение. Худший случай: имя последнее или его нет → 50 сравнений. Линейный поиск это O(n).
2. Какое наибольшее число сравнений нужно бинарному поиску в упорядоченном списке из 1024 элементов?
Каждый шаг делит список пополам: 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1. Это 10 делений, плюс последняя проверка: не больше 11 сравнений (log₂ 1024 = 10).
3. Найдите Big O для f(n) = 4n² + 10n + 7.
Оставляем самое большое слагаемое (4n²) и отбрасываем константу 4: O(n²).
4. Цикл по i идёт от 1 до n, а внутри него другой цикл по j идёт от 1 до n. Сколько раз выполнится строка во внутреннем цикле?
n раз для каждого из n значений i: n × n = n². Временная сложность O(n²).
5. Программа с O(n²) сортирует 1000 элементов за 2 секунды. Примерно сколько времени она займёт для 3000 элементов?
n становится в 3 раза больше, значит n² становится в 3² = 9 раз больше: примерно 2 × 9 = 18 секунд.
6. Сравните пузырьковую сортировку и сортировку слиянием для n = 1000 элементов.
Пузырьковая: около n²/2 = 500 000 сравнений. Слиянием: около n log₂ n = 1000 × 10 = 10 000. Сортировка слиянием делает примерно в 50 раз меньше работы, но ей нужна дополнительная память.
Частые ошибки
- Измерять скорость только секундомером на одном компьютере. Лучше считать шаги в зависимости от n.
- Использовать бинарный поиск в неупорядоченном списке. Его предусловие: список упорядочен.
- Оставлять константы в Big O, например писать O(2n). Это просто O(n).
- Писать рекурсивную функцию без базового случая или такую, которая не уменьшает задачу.