"О большое"
Мы описывали трудоемкость алгоритма в зависимости от n, количества входных элементов. Поиск в неотсортированных данных занимает время, пропорциональное n; при использовании двоичного поиска по отсортированным данным время будет пропорционально log n. Время сортировки пропорционально n2 или n logn.
Нам нужно как-то уточнить эти высказывания, при этом абстрагируясь от таких деталей, как скорость процессора и качество компилятора (и программиста). Хотелось бы сравнивать время работы и затраты памяти алгоритмов вне зависимости от языка программирования, компилятора, архитектуры компьютера, скорости процессора, загруженности системы и других сложных факторов.
Для этой цели существует стандартная форма записи, которая называется "О большое". Основной параметр этой записи – n, размер входных данных, а сложность или время работы алгоритма выражается как функция от n. "О" – от английского order, то есть порядок. Например, фраза "Двоичный поиск имеет сложность 0(log n)" означает, что для поиска в массиве из n элементов требуется порядка log n действий. Запись О(f(n)) предусматривает, что при достаточно больших n время выполнения пропорционально f(n), не быстрее, например, О(n2) или 0(n log n). Асимптотические оценки вроде этой полезны при теоретическом анализе и грубом сравнении алгоритмов, однако на практике разница в деталях может иметь большое значение. Например, алгоритм класса 0(n2) с малым количеством дополнительных вычислений для малых п может работать быстрее, чем сложный алгоритм класса О(n logn), однако при достаточно большом п алгоритм с медленнее возрастающей функцией поведения неизбежно будет работать быстрее.
Нам нужно различать также случаи наихудшего и ожидаемого поведения. Трудно строго определить, что такое "ожидаемое" поведение, потому что определение зависит от наших предположений о возможных входных данных. Обычно мы можем точно указать самый плохой случай, хотя иногда и здесь можно ошибиться. Для quicksort в самом плохом случае время работы растет как О(n2), а среднее ("ожидаемое") время – как О(n log n). Если каждый раз аккуратно выбирать элемент-разделитель, то мы можем свести вероятность квадратичного (то есть 0(n2)) поведения практически к нулю; хорошо реализованная quicksort действительно обычно ведет себя как О(n log n).
Вот основные случаи:
| Запись | Название времени | Пример |
|---|---|---|
| O(1) | Константное | Индексирование массива |
| O(log n) | Логарифмическое | Двоичный поиск |
| O(n) | Линейное | Сравнение строк |
| O(n log n) | n logn | Quicksort |
| O(n2) | Квадратичное | Простые методы сортировки |
| О(n3) | Кубическое | Перемножение матриц |
| O(2n) | Экспоненциальное | Перебор всех подмножеств |
Доступ к элементу в массиве – операция, работающая за константное (О(1)) время. Алгоритм, за каждый шаг отсеивающий половину входных данных, как двоичный поиск, обычно займет время O(log n). Сравнение двух строк длиной в n символов с помощью strcmp займет О(n).
Традиционный алгоритм перемножения двух квадратных матриц порядка n занимает О(n2), поскольку каждый элемент получается в результате перемножения и пар чисел и суммирования результатов, а всего элементов n2.
Экспоненциальное время работы алгоритма обычно является результатом перебора всех вариантов: у множества из n элементов – 2n различных подмножеств, поэтому алгоритм, которому надо пройтись по всем подмножествам, будет выполняться за время 0(2n), то есть будет экспоненциальным. Экспоненциальные алгоритмы обычно слишком долго работают, если только п не очень мало, поскольку добавление одного элемента удваивает время работы алгоритма. К сожалению, существует много задач, таких как, например, знаменитая "задача коммивояжера", для которых известны только экспоненциальные решения. Когда задача такова, часто вместо точных решений берут алгоритмы, находящие некоторое приближение к ответу.
Упражнение 2.3
Каковы входные данные для алгоритма quicksort, которые заставляют его работать медленнее всего, как в наихудшем случае? Попробуйте найти несколько наборов данных, сильно замедляющих библиотечную версию алгоритма. Автоматизируйте процесс, чтобы вы легко могли задавать параметры и проводить большое число экспериментов.
Упражнение 2.4
Придумайте и реализуйте алгоритм, который будет сортировать массив из п целых как можно медленнее. Только напишите его честно: алгоритм должен постепенно прогрессировать и в конце концов завершиться, и ваша реализация не должна использовать всяческие трюки вроде лишних пустых циклов. Какова получилась сложность вашего алгоритма как функция от n?