В табл. 1.2 приведены некоторые функции, которые наиболее часто исполь-
зуются для вычисления сложности. Функции перечислены в порядке возраста-
ния сложности. Это значит, что алгоритмы со сложностью, вычисляемой с помо-
щью функций, которые помещены вверху таблицы, будут выполняться быстрее
алгоритмов, сложность которых вычисляется с помощью ниже расположенных
функций.
Таблица 1.2. Общие функции оценки сложности
Таким образом, уравнение сложности, которое содержит несколько этих функ-
ций, при приведении в систему оценки сложности по порядку величины будет со-
кращаться до функции, расположенной ниже в таблице. Например, O(log(N) + N^2) —
это то же самое, что и О(N^2).
Сможет ли алгоритм работать быстрее, зависит от того, как вы его используе-
те. Если вы запускаете алгоритм раз в год для решения задач с достаточно малыми
объемами данных, то вполне приемлема производительность О(N^2). Если же алго-
ритм выполняется под наблюдением пользователя в интерактивном режиме, опе-
рируя большими объемами данных, то может быть недостаточно и производитель-
ности O(N).
Обычно алгоритмы со сложностью N * log(N) работают с очень хорошей ско-
ростью. Алгоритмы со сложностью N^c при небольших значениях С, например N^2,
применяются, когда объемы данных ограничены. Вычислительная сложность ал-
горитмов, порядок которых определяется функциями C^N и N! очень велика, поэто-
му эти алгоритмы пригодны только для решения задач с очень малым объемом
перерабатываемой информации.
Один из способов рассмотрения относительных размеров этих функций за-
ключается в определении времени, которое требуется для решения задач различных
размеров. Табл. 1.3 показывает, как долго компьютер, осуществляющий миллион
операций в секунду, будет выполнять некоторые медленные алгоритмы. Из таб-
лицы видно, что только небольшие задачи можно решить с помощью алгоритмов
со сложностью O(C^N), и самые маленькие — с помощью алгоритмов со сложнос-
тью O(N!). Для решения задач порядка O(N!), где N = 24, потребовалось бы боль-
ше времени, чем существует вселенная.
Таблица 1.3. Время выполнения сложных алгоритмов
Скорость работы алгоритма в реальных условиях
Несмотря на то, что малые члены и постоянные множители отбрасываются при
изучении сложности алгоритмов, часто их необходимо учитывать для фактичес-
кого написания программ. Эти числа становятся особенно важными, когда размер
задачи мал, а константы большие.
Предположим, нужно рассмотреть два алгоритма, которые выполняют одну
и ту же задачу. Первый выполняет ее за время O(N), а второй — за время O(N^2).
Для больших N первый алгоритм, вероятно, будет работать быстрее.
При более близком рассмотрении обнаруживается, что первый описывается
функцией f(N) = 30 * N + 7000, а второй — f(N) = N^2. В этом случае второй алго-
ритм при N меньше 100 существенно быстрее. Если вы знаете, что размер данных
задачи не превышает 100, то целесообразнее использовать второй алгоритм.
С другой стороны, время выполнения разных инструкций может сильно- отли-
чаться. Если первый алгоритм использует быстрые операции с памятью, а второй —
медленное обращение к диску, то первый алгоритм будет эффективнее в любом
случае.
Проблему выбора оптимального алгоритма осложняют и другие факторы. На-
пример, первый алгоритм может требовать больше памяти, чем установлено на
компьютере. Но на реализацию второго алгоритма, если он гораздо сложнее, мо-
жет уйти больше времени, а его отладка превратится в настоящий кошмар. Иногда
подобные практические соображения могут сделать теоретический анализ слож-
ности алгоритма почти бессмысленным.
Тем не менее анализ сложности помогает понять особенности алгоритмов и опре-
делить, в каком месте программы производится большая часть вычислений. Усовер-
шенствовав код в этих частях, можно существенно увеличить производительность
программы в целом.
Иногда лучшим способом для определения наиболее эффективного алгорит-
ма является тестирование. При этом важно, чтобы использовались данные, макси-
мально приближенные к реальным условиям. В обратном случае результаты тес-
тирования могут сильно отличаться от действительных.
Читать дальше >>