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