Асимптотический порядок роста - Основы анализа алгоритмов

Итак, наше обсуждение вычислительной разрешимости по своей сути базируется на способности выражения того, что худшее время выполнения алгоритма для входных данных размера nрастет со скоростью, которая не более чем пропорциональна некоторой функции f(n). Функция f(n) становится граничной оценкой времени выполнения алгоритма. Теперь нужно заложить основу для дальнейшего рассмотрения этой концепции.

Алгоритмы будут в основном выражаться на псевдокоде наподобие того, который использовался в алгоритме Гейла-Шепли. Время от времени появляется необходимость в более формальных средствах, но для большинства целей такого стиля определения алгоритмов вполне достаточно. Вычисляя граничную оценку для времени выполнения алгоритма, мы будем подсчитывать количество выполняемых шагов псевдокода; в этом контексте один шаг будет состоять из присваивания значения переменной, поиска элемента в массиве, перехода по указателю или выполнения арифметической операции с целым числом фиксированного размера.

Если нам потребуется что-то сказать о времени выполнения алгоритма с входными данными размера n, можно попытаться сделать предельно конкретное заявление, например: “Для любых входных данных размера n этот алгоритм будет выполнен не более чем за 1,62n² + 3,5n + 8 шагов”. В некоторых контекстах такое утверждение будет представлять интерес, но в общем случае ему присущ ряд недостатков. Во-первых, получение такой точной оценки может потребовать значительных усилий, а настолько подробная оценка все равно не нужна. Во-вторых, так как нашей конечной целью является идентификация широких классов алгоритмов, обладающих сходным поведением, нам хотелось бы различать время выполнения с меньшим уровнем детализации, чтобы сходство между разными алгоритмами (и разными задачами) проявлялось более наглядно. И наконец, излишне точные утверждения о количестве шагов алгоритма часто оказываются (в некоторой степени) бессмысленными. Как говорилось ранее, мы обычно подсчитываем шаги в описании алгоритма на псевдокоде, напоминающем язык программирования высокого уровня. Каждый из этих шагов обычно преобразуется в некоторое фиксированное число примитивных шагов при компиляции программы в промежуточное представление, которые затем преобразуются в еще большее количество шагов в зависимости от конкретной архитектуры, используемой для проведения вычислений. Итак, максимум, что можно сказать с уверенностью, — что при рассмотрении задачи на разных уровнях вычислительной абстракции понятие “шаг” может увеличиваться или уменьшаться с постоянным коэффициентом. Например, если для выполнения одной операции языка высокого уровня требуется 25 низкоуровневых машинных команд, то наш алгоритм, выполняемый за максимум 1,62n² + 3,5n + 8 шагов, может рассматриваться как выполняемый за 40,5n² + 87,5n + 200 шагов при анализе на уровне, приближенном к уровню физического оборудования.

O, Ω и Ө

По всем указанным причинам мы хотим выразить скорость роста времени выполнения и других функций способом, из которого исключены постоянные факторы и составляющие низших порядков. Иначе говоря, нам хотелось бы взять время выполнения типа приведенного выше, 1,62n² + 3,5n + 8, и сказать, что оно растет со скоростью n². А теперь посмотрим, как же решается эта задача.

Асимптотические верхние границы

Пусть T(n) — функция (допустим, время выполнения в худшем случае для некоторого алгоритма) с входными данными размера n. (Будем считать, что все рассматриваемые функции получают неотрицательные значения.) Для другой функции f(n) говорится, что T(n) имеет порядок f(n) (в условной записи O(f(n)), если для достаточно больших n функция T(n) ограничивается сверху произведением f(n) на константу. Также иногда используется запись T(n) = O(f(n)). А если выражаться точнее, функция T(n) называется имеющей порядок O(f (n)), если существуют такие константы c > 0 и n₀ ≥ 0, что для всех n ≥ n₀ выполняется условие T(n) ≤ c ∙ f (n). В таком случае говорят, что T имеет асимптотическую верхнюю границу f. Важно подчеркнуть, что это определение требует существования константы c, работающей для всех n; в частности, c не может зависеть от n.

В качестве примера того, как это определение используется для выражения верхней границы времени выполнения, рассмотрим алгоритм, время выполнения которого (как в предшествующем обсуждении) задается в форме T(n) = pn² + qn + r для положительных констант p, q и r. Мы утверждаем, что любая такая функция имеет O(n²). Чтобы понять, почему это утверждение справедливо, следует заметить, что для всех n ≥ 1 истинны условия qn ≤ qn², и r ≤ rn². Следовательно, можно записать

T(n) = pn² + qn + r ≤ Pn² + qn² + rn² = (p + q + r)n²

для всех n ≥ 1. Это неравенство в точности соответствует требованию определения O(∙): T(n) ≤ cn², где c = p + q + r.

Учтите, что запись O(∙) выражает только верхнюю границу, а не точную скорость роста функции. Например, по аналогии с утверждением, что функция T(n) = pn² + qn + r имеет O(n²), также будет правильно утверждать, что она имеет O(n³). В самом деле, мы только что выяснили, что T(n) < (p + q + r)n², а поскольку также n² ≤ n³, можно заключить, что T(n) ≤ (p + q + r)n³, как того требует определение O(n³). Тот факт, что функция может иметь много верхних границ, — не просто странность записи; он также проявляется при анализе времени выполнения. Встречались ситуации, в которых алгоритм имел доказанное время выполнения O(n³); проходили годы, и в результате более тщательного анализа того же алгоритма выяснялось, что в действительности время выполнения было равно O(n²). В первом результате не было ничего ошибочного; он определял правильную верхнюю границу. Просто эта оценка времени выполнения была недостаточно точной.

Асимптотические нижние границы

Для нижних границ тоже существует парное обозначение. Часто при анализе алгоритма (допустим, было доказано, что время выполнения для худшего случая T(n) имеет порядок O(n²)) бывает нужно показать, что эта верхняя граница является лучшей из возможных. Для этого следует выразить условие, что для входных данных произвольно большого размера n функция T(n) не меньше произведения некой конкретной функции f(n) на константу. (В данном примере в роли f(n) оказывается n²). Соответственно говорят, что T(n) имеет нижнюю границу Ω(f(n)) (также используется запись T(n) = Ω(f(n))), если существуют такие константы е > 0 и n₀ ≥ 0, что для всех n ≥ n₀ выполняется условие T(n) ≥ е ∙ f(n). По аналогии с записью O(∙) мы будем говорить, что T в таком случае имеет асимптотическую нижнюю границу f. И снова следует подчеркнуть, что константа е должна быть фиксированной и не зависящей от n.

Это определение работает точно так же, как O(∙), не считая того, что функция T(n) ограничивается снизу, а не сверху. Например, возвращаясь к функции T(n) = pn² + qn + r, где p, q и r — положительные константы, будем утверждать, что T(n) = Ω(n²). Если при установлении верхней границы приходилось “раздувать” функцию T(n) до тех пор, пока она не начинала выглядеть как произведение n² на константу, на этот раз нужно сделать обратное: “подрезать” T(n), пока она не начнет выглядеть как произведение n² на константу. Сделать это несложно; для всех n ≥0

T(n) = pn² + qn + r ≥ pn²,

что соответствует требованию определения Ω(∙) с е = p > 0.

Для нижних границ существует то же понятие “точности” и “слабости”, что и для верхних. Например, будет правильно утверждать, что функция T(n) = pn² + qn + r имеет Ω(n), так как T(n) ≥ pn² ≥ pn.

Асимптотические точные границы

Если можно показать, что время выполнения T(n) одновременно характеризуется O(f(n)) и Ω(f(n)), то возникает естественное ощущение, что найдена “правильная” граница: T(n) растет в точности как f(n) в пределах постоянного коэффициента. Например, к такому выводу можно прийти из того факта, что T(n) = pn² + qn + r одновременно имеет O(n²) и Ω(n²).

Для выражения этого понятия тоже существует специальная запись: если функция T(n) одновременно имеет O(f(n)) и Ω(f(n)), говорят, что T(n) имеет Ө(f(n)), а f(n) называется асимптотически точной границей для T(n). Итак, например, приведенный выше анализ показывает, что T(n) = pn² + qn + r имеет Ө(n²).

Асимптотически точные границы для худшего времени выполнения полезны, поскольку они характеризуют быстродействие алгоритма в худшем случае с точностью до постоянного множителя. И, как следует из определения Ө(∙), такие границы могут быть получены сокращением промежутка между верхней и нижней границами. Например, иногда приходится читать (отчасти неформально выраженные) утверждения вида “Показано, что в худшем случае время выполнения алгоритма имеет верхнюю границу O(n³), однако не существует известных примеров, для которых алгоритм выполняется за более чем Ω(n²) шагов”. Такое утверждение можно считать неявным предложением поискать асимптотически точную границу для худшего времени выполнения алгоритма.

Иногда асимптотически точная граница может быть вычислена напрямую, как предел при стремлении n к бесконечности. Фактически если отношение функций f(n) и g(n) сходится к положительной константе, когда n уходит в бесконечность, то f(n) = Ө(g(n)).

(2.1) Имеются две функции f и g, для которых

существует и равен некоторому числу c > 0. Тогда f(n) = Ө(g(n)).

Доказательство. Мы воспользуемся тем фактом, что предел существует и он положителен, чтобы показать, что f (n) = O(g(n)) и f (n) = Ω(g(n)), как того требует определение Ω(∙).

Поскольку

из определения предела следует, что существует некоторое значение n₀, начиная с которого отношение всегда лежит в диапазоне между 1/2c и 2с. Таким образом, f(n) ≤ 2cg(n) для всех n > n₀, из чего следует, что f(n) = O(g(n)); а f(n) ≥ 1/2cg(n) — для всех n ≥ n₀, из чего следует, что f(n) = Ω(g(n)). ■

Свойства асимптотических скоростей роста

После знакомства с определениями O, Ω и Ө будет полезно рассмотреть некоторые из их основных свойств.

Транзитивность

Первое свойство — транзитивность: если функция f асимптотически ограничена сверху функцией g, а функция g, в свою очередь, асимптотически ограничена сверху функцией h, то функция fасимптотически ограничена сверху функцией h. Аналогичное свойство действует и для нижних границ. Более точно это можно записать в следующем виде.

(2.2)

(a) Если f = O(g) и g = O(h), то f = O(h).

(b) Если f = Ω(g) и g = Ω(h), то f = Ω(h).

Доказательство. Мы ограничимся частью (а) этого утверждения; часть (б) доказывается практически аналогично.

Для (а) известно, что для некоторых констант c и n₀ выполняется условие f(n) ≤ cg(n) для всех n ≥ n₀. Кроме того, для некоторых (возможно, других) констант с' и n₀' выполняется условие g(n) ≤ c'h(n) для всех n ≥ n₀'. Возьмем любое число n, не меньшее как n₀, так и n₀'. Известно, что f(n) ≤ cg(n) ≤ сс'h(n), поэтому f(n) ≤ cc'h(n) для всех n ≥ max(n₀, n₀'). Из последнего неравенства следует, что f = O(h). ■

Объединяя части (а) и (b) в (2.2), можно прийти к аналогичному результату для асимптотически точных границ. Допустим, известно, что f = Ө(g), а g = Ө(h). Так как f = O(g) и g = O(h), из части (а) известно, что f = O(h); а поскольку f = Ω(g) и g = Ω(h), из части (б) следует, что f = Ω(h). Таким образом, f = Ө(h). Следовательно, мы показали, что

(2.3) Если f = Ө(g) и g = Ө(h), то f = Ө(h).

Суммы функций

Также полезно иметь количественную оценку эффекта суммирования двух функций. Прежде всего, если имеется асимптотическая верхняя оценка, применимая к каждой из двух функций f и g, то она применима и к сумме этих функций.

(2.4) Предположим, f и g — такие две функции, что для некоторой функции h выполняются условия f = O(h) и g = O(h). В этом случае f + g = O(h).

Доказательство. Из постановки задачи следует, что для некоторых констант c и n₀ выполняется условие f(n) ≤ ch(n) для всех n ≥ n₀. Кроме того, для некоторых (возможно, других) констант c' и n₀' выполняется условие g(n) ≤ c'h(n) для всех n ≥ n₀'. Возьмем любое число n, не меньшее как n₀, так и n₀'. Известно, что f(n) + g(n) ≤ ch(n) + c'h(n). Из этого следует, что f(n) + g(n) ≤ (c + c')h(n) для всех n ≥ max(n₀, n₀'). Из последнего неравенства следует, что f + g = O(h). ■

Это свойство обобщается для суммы фиксированного числа функций k, где k может быть больше двух. Точная формулировка результата приведена ниже; доказательство не приводится, так как оно, по сути, повторяет доказательство (2.4) для сумм, состоящих из к слагаемых вместо 2.

(2.5) Пусть k — фиксированная константа, а f₁, f₂, ..., f_k и h — функции, такие что f_i = O(h) для всех i. В этом случае f₁ + f₂ + ...+ f_k = O(h).

У (2.4) имеется следствие, которое проявляется в типичной ситуации: во время анализа алгоритма, состоящего из двух высокоуровневых частей, часто удается легко показать, что одна из двух частей медленнее другой. В этом случае время выполнения всего алгоритма асимптотически сравнимо со временем выполнения медленной части. Поскольку общее время выполнения представляет собой сумму двух функций (время выполнения двух частей), полученные выше результаты для асимптотических границ сумм функций напрямую применимы в данном случае.

(2.6) Предположим, f и g — две функции (получающие неотрицательные значения) и g = O(f). В этом случае f + g = Ө(f). Другими словами, f является асимптотически точной границей для объединенной функции f + g.

Доказательство. Очевидно, f + g = Ω(f), так как для всех n ≥ 0 выполняется условие f(n) + g(n) ≥ f(n). Чтобы завершить доказательство, необходимо показать, что f + g = O(f).

Но это утверждение является прямым следствием (2.4): дано, что g = O(f), а условие f = O(f) выполняется для любой функции, поэтому из (2.4) следует f + g = O(f). ■

Данный результат также распространяется на сумму любого фиксированного количества функций: самая быстрорастущая из функций является асимптотически точной границей для суммы.

Асимптотические границы для некоторых распространенных функций

Некоторые функции постоянно встречаются при анализе алгоритмов, поэтому будет полезно изучить асимптотические свойства основных разновидностей: полиномиальных, логарифмических и экспоненциальных.

Полиномиальные функции

Напомним, что полиномиальной называется функция, которая может быть записана в форме f(n) = a₀ + a₁n + a₂n² +...+ a_dn^d для некоторой целочисленной константы d > 0, где последний коэффициент a_d отличен от нуля. Значение d называется степенью (или порядком) полинома. Например, упоминавшиеся ранее функции вида pn² + qn + r (где p ≠ 0) представляют собой полиномиальные функции со степенью 2.

Основная особенность полиномиальных функций заключается в том, что их асимптотическая скорость роста детерминируется “членом высшего порядка” — то есть слагаемым, определяющим степень. Это утверждение более формально определяется в следующем утверждении. Так как нас интересуют только функции, получающие неотрицательные значения, наше внимание будет ограничено полиномиальными функциями, у которых член высшего порядка имеет положительный коэффициент a_d > 0.

(2.7) Предположим, f является полиномиальной функцией степени d с положительным коэффициентом a_d. В этом случае f = O(n^d).

Доказательство. Условие записывается в виде f = a₀ + a₁n + a₂n² + ...+ a_dn^d, где a_d > 0. Верхняя граница напрямую следует из (2.5). Во-первых, следует заметить, что коэффициенты a_j для j < d могут быть отрицательными, но в любом случае a_jn^j ≤ │a_j│n^d для всех n ≥ 1. Следовательно, каждый член полинома имеет O(n^d). Так как f представляет собой сумму фиксированного количества функций, каждая из которых имеет O(n^d), из (2.5) следует, что f = O(n^d). ■

Также можно показать, что по условиям (2.7) f = Ω(n^d), из чего следует, что фактически f = Ө(n^d).

Это свойство играет важную роль для рассмотрения отношения между асимптотическими границами такого рода и понятием полиномиального времени, к которому мы пришли в предыдущем разделе, для формализации более расплывчатого понятия эффективности. В записи O(∙) можно легко дать определение полиномиального времени: алгоритмом с полиномиальным временем называется алгоритм, время выполнения которого T(n) = O(n^d) для некоторой константы d, не зависящей от размера входных данных.

Таким образом, алгоритмы с границами времени выполнения вида O(n²) и O(n³) являются алгоритмами с полиномиальным временем. Однако важно понимать, что алгоритм может выполняться с полиномиальным временем даже в том случае, если время выполнения не записывается в форме n в целочисленной степени. Прежде всего, многие алгоритмы имеют время выполнения в форме O(n^x) для некоторого числа х, которое не является целым. Например, в главе 5 представлен алгоритм с временем выполнения O(n^1,59); также встречаются экспоненты меньшие 1, как в границах типа O(√n) = O(n^1/2).

Другой распространенный пример: часто встречаются алгоритмы, время выполнения которых записывается в форме O(n log n). Такие алгоритмы также имеют полиномиальное время выполнения: как будет показано далее, log n ≤ n для всех n ≥ 1, а следовательно, n log n ≤ n² для всех n ≥ 1. Другими словами, если алгоритм имеет время выполнения O(n log n), он также имеет время выполнения O(n²), а следовательно, является алгоритмом с полиномиальным временем.

Логарифмические функции

Напомним, что логарифм n по основанию b — log_b n — равен такому числу х, что b^x = n. Чтобы получить примерное представление о скорости роста log_b n, можно заметить, что при округлении вниз до ближайшего целого числа логарифм на 1 меньше количества цифр в представлении n по основанию b (таким образом, например, значение 1 + log₂ n с округлением вниз определяет количество битов, необходимых для представления n).

Итак, логарифмические функции растут очень медленно. В частности, для каждого основания b функция log_b n асимптотически ограничивается всеми функциями вида n^x, даже для (дробных) значений х, сколь угодно близких к 0.

(2.8) Для всех b > 1 и всех х > 0 выполняется условие log_b n = O(n^x).

Логарифмы могут напрямую преобразовываться к другому основанию по следующей фундаментальной формуле:

Эта формула объясняет, почему границы часто записываются в виде O(log n) без указания основания логарифма. Не стоит рассматривать это как неточность записи: из приведенной формулы следует, что а это означает, что log_a n = Ө(log_b n). Следовательно, при использовании асимптотической записи основание алгоритма роли не играет.

Экспоненциальные функции

Экспоненциальные функции записываются в форме f(n) = rⁿ для некоторого постоянного основания r. Здесь нас интересует случай r > 1, что приводит к исключительно быстрому росту функции.

Если полиномиальная функция возводит n в фиксированную степень, экспоненциальная функция возводит фиксированное число в степень n; скорость роста при этом сильно увеличивается. Один из способов описания отношений между полиномиальными и экспоненциальными функциями представлен ниже.

(2.9) Для всех r > 1 и всех d > 0 выполняется условие n^d = O(rⁿ).

В частности, любая экспоненциальная функция растет быстрее любой полиномиальной. И как было показано в табл. 2.1, при подстановке реальных значений n различия в скорости роста становятся весьма впечатляющими.

По аналогии с записью O(log n) без указания основания часто встречаются формулировки вида “Алгоритм имеет экспоненциальное время выполнения” без указания конкретной экспоненциальной функции. В отличие от свободного использования log n, оправданного игнорированием постоянных множителей, такое широкое использование термина “экспоненциальный” несколько неточно. В частности, для разных оснований r > s > 1 никогда не выполняется условие rⁿ = Ө(sⁿ). В самом деле, для этого бы потребовалось, чтобы для некоторой константы с > 0 выполнялось условие rⁿ ≤ csⁿ для всех достаточно больших n. Но преобразование этого неравенства дает (r/s)ⁿ ≤ c для всех достаточно больших n. Так как r > s, выражение (r/s)ⁿ стремится к бесконечности с ростом n, поэтому оно не может ограничиваться константой с.

Итак, с асимптотической точки зрения все экспоненциальные функции различны. Тем не менее обычно смысл неточной формулировки “Алгоритм имеет экспоненциальное время выполнения” понятен — имеется в виду, что время выполнения растет по крайней мере со скоростью некоторой экспоненциальной функции, а все экспоненциальные функции растут так быстро, что алгоритм можно попросту отбросить, не вдаваясь в подробности относительно точного времени выполнения. Это не всегда оправданно — в некоторых случаях за экспоненциальными алгоритмами скрывается больше, чем видно на первый взгляд (как мы увидим, например, в главе 10); но как указано в первой части этой главы, это разумное эмпирическое правило.

Итак, логарифмические, полиномиальные и экспоненциальные функции служат полезными ориентирами в диапазоне функций, встречающихся при анализе времени выполнения. Логарифмические функции растут медленнее полиномиальных, а полиномиальные растут медленнее экспоненциальных.