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

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

Это определение работает точно так же, как O(), не считая того, что функ- ция T(n) ограничивается снизу, а не сверху. Например, возвращаясь к функции T(n) = рn2 + qn + r, гдер, q и r — положительные константы, будем утверждать, что T(n) = Ω(n2). Если при установлении верхней границы приходилось «раздувать» функцию T(n) до тех пор, пока она не начинала выглядеть как произведение n2 на константу, на этот раз нужно сделать обратное: «подрезать» T(n), пока она не начнет выглядеть как произведение n2 на константу. Сделать это несложно; для всех n > 0

T(n) = рn2 + qn + r > рn2,

что соответствует требованию определения Ω(·) с е = р > 0.

Для нижних границ существует то же понятие «точности» и «слабости», что и для верхних. Например, будет правильно утверждать, что функция T(n) = рn2 + qn + r имеет Ω(n), так как T(n) >рn2 >рn.

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

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

  1. НИЖНИЕ ЧАКРЫ
  2. Я-ГРАНИЦА
  3. Границы эго
  4. Границы
  5. § 7. Смежные права и их границы
  6. Часть I. Границы Ума
  7. § 5. Границы исключительных авторских прав
  8. Нарушение границы
  9. Нарушение границы
  10. Царство без границ
  11. Границы домов
  12. УСТАНОВИВ ГРАНИЦЫ, ИХ СЛЕДУЕТ УВАЖАТЬ
  13. 2. Границы исключительных патентных прав
  14. 9.1. ПАМЯТЬ БЕЗ ГРАНИЦ
  15. V. 2. 4. Границы адекватности модели.
  16. Статья 13. Границы осуществления гражданских прав
  17. 7. Границы и срок действия смежных прав
  18. ВЫ ЗАКЛЮЧЕНЫ В ГРАНИЦАХ СВОЕЙ "ОШИБОЧНОЙ УВЕРЕННОСТИ"
  19. VC8 - "божественная граница", расположена в центре пупка.
  20. ВОЛЬНАЯ РУССКАЯ ПРЕССА ЗА ГРАНИЦЕЙ. «ПОЛЯРНАЯ ЗВЕЗДА» И «КОЛОКОЛ» А.И. ГЕРЦЕНА