Асимптотические верхние границы
В качестве примера того, как это определение используется для выражения верхней границы времени выполнения, рассмотрим алгоритм, время выполнения которого (как в предшествующем обсуждении) задается в форме 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). В первом результате не было ничего ошибочного; он определял правильную верх- нюю границу. Просто эта оценка времени выполнения была недостаточно точной.
Еще по теме Асимптотические верхние границы:
- ВЕРХНИЙ МИР
- ПОРОГ ВОСПРИЯТИЯ ВЕРХНИЙ АБСОЛЮТНЫЙ
- ВЕРХНИЕ ЧАКРЫ
- ПУТЬ В ВЕРХНИЙ МИР
- Делаем верхнюю часть.
- ПОСЕЩЕНИЕ ВЕРХНЕГО МИРА
- ПЯТЬ УРОВНЕЙ ВЕРХНЕГО МИРА
- Упражнение ПУТЕШЕСТВИЕ В ВЕРХНИЙ МИР
- ПЯТЬ УРОВНЕЙ ВЕРХНЕГО МИРА
- ВЫБОРЫ ВЕРХНЕГО И НИЖНЕГО ПОРЯДКОВ