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

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

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

Асимптотически точные границы для худшего времени выполнения полезны, поскольку они характеризуют быстродействие алгоритма в худшем случае с точно- стью до постоянного множителя. И, как следует из определения Θ(), такие границы могут быть получены сокращением промежутка между верхней и нижней грани- цами. Например, иногда приходится читать (отчасти неформально выраженные) утверждения вида «Показано, что в худшем случае время выполнения алгоритма имеет верхнюю границу O(n3), однако не существует известных примеров, для которых алгоритм выполняется за более чем Ω(n2) шагов». Такое утверждение можно считать неявным предложением поискать асимптотически точную границу для худшего времени выполнения алгоритма.

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

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


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

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

Поскольку


из определения предела следует, что существует некоторое значение ;?0, начиная с которого отношение всегда лежит в диапазоне между и 2с. Таким образом,

/(;?) < 2сg(п) для всех n > ;?0, из чего следует, что f{п)=О{g{п)); а/(;?) > — ⅞(п) для всех n > ;?0, из чего следует, что/(;?) = Ω,(g(п)). ■

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

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

  1. Я-ГРАНИЦА
  2. Границы эго
  3. Границы
  4. § 7. Смежные права и их границы
  5. Часть I. Границы Ума
  6. § 5. Границы исключительных авторских прав
  7. Нарушение границы
  8. Нарушение границы
  9. Царство без границ
  10. Границы домов
  11. УСТАНОВИВ ГРАНИЦЫ, ИХ СЛЕДУЕТ УВАЖАТЬ