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

Пусть T(n) — функция (допустим, время выполнения в худшем случае для некото- рого алгоритма) с входными данными размера n. (Будем считать, что все рассматри- ваемые функции получают неотрицательные значения.) Для другой функции f (n) говорится, что T(n) имеет порядок f (n) (в условной записи O( f (n)), если для достаточно больших n функция T(n) ограничивается сверху произведением f (n) на константу.

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

T(n) = pn2 + qn + r ≤ P n2 + qn2 + rn2 = (p + q + r)n2 для всех n ≥ 1. Это неравенство в точности соответствует требованию определе- ния O(·): T(n) ≤ cn2, где c = p + q + r.

Учтите, что запись O(·) выражает только верхнюю границу, а не точную ско- рость роста функции. Например, по аналогии с утверждением, что функция T(n) = pn2 + qn + r имеет O(n2), также будет правильно утверждать, что она имеет O(n3).

В самом деле, мы только что выяснили, что T(n) ≤ (p + q + r)n2, а поскольку также n2 ≤ n3, можно заключить, что T(n) ≤ (p + q + r)n3, как того требует опреде- ление O(n3). Тот факт, что функция может иметь много верхних границ, — не про- сто странность записи; он также проявляется при анализе времени выполнения.

Встречались ситуации, в которых алгоритм имел доказанное время выполнения O(n3); проходили годы, и в результате более тщательного анализа того же алгоритма выяснялось, что в действительности время выполнения было равно O(n2). В первом результате не было ничего ошибочного; он определял правильную верх- нюю границу. Просто эта оценка времени выполнения была недостаточно точной.