Асимптотические верхние границы
Пусть 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). В первом результате не было ничего ошибочного; он определял правильную верх- нюю границу. Просто эта оценка времени выполнения была недостаточно точной.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу