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

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

В качестве примера того, как это определение используется для выражения верхней границы времени выполнения, рассмотрим алгоритм, время выполнения которого (как в предшествующем обсуждении) задается в форме T(n) = pn2 + qп + r для положительных констант р, q и r. Мы утверждаем, что любая такая функция имеет O(n2). Чтобы понять, почему это утверждение справедливо, следует заме-

тить, что для всех n > 1 истинны условия qn < qn2, и r < rn2. Следовательно, можно записать

T(n) = pn2 + qп + r < P n2 + qп2 + rn2 = (р + q + r)п2

для всех n > 1. Это неравенство в точности соответствует требованию определе- ния O(): T(n) < cn2, где c = р + q + r.

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

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

  1. ВЕРХНИЙ МИР
  2. ПОРОГ ВОСПРИЯТИЯ ВЕРХНИЙ АБСОЛЮТНЫЙ
  3. ВЕРХНИЕ ЧАКРЫ
  4. ПУТЬ В ВЕРХНИЙ МИР
  5. Делаем верхнюю часть.
  6. ПОСЕЩЕНИЕ ВЕРХНЕГО МИРА
  7. ПЯТЬ УРОВНЕЙ ВЕРХНЕГО МИРА
  8. Упражнение ПУТЕШЕСТВИЕ В ВЕРХНИЙ МИР
  9. ПЯТЬ УРОВНЕЙ ВЕРХНЕГО МИРА
  10. ВЫБОРЫ ВЕРХНЕГО И НИЖНЕГО ПОРЯДКОВ