"О большое" Мы описывали трудоемкость алгоритма в зависимости от п, количества входных элементов. Поиск в неотсортированных данных занимает время, пропорциональное п; при использовании двоичного поиска по отсортированным данным время будет пропорционально 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?