Асимптотические нижние границы
Это определение работает точно так же, как 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.
Еще по теме Асимптотические нижние границы:
- НИЖНИЕ ЧАКРЫ
- Я-ГРАНИЦА
- Границы эго
- Границы
- § 7. Смежные права и их границы
- Часть I. Границы Ума
- § 5. Границы исключительных авторских прав
- Нарушение границы
- Нарушение границы
- Царство без границ
- Границы домов
- УСТАНОВИВ ГРАНИЦЫ, ИХ СЛЕДУЕТ УВАЖАТЬ
- 2. Границы исключительных патентных прав
- 9.1. ПАМЯТЬ БЕЗ ГРАНИЦ
- V. 2. 4. Границы адекватности модели.
- Статья 13. Границы осуществления гражданских прав
- 7. Границы и срок действия смежных прав
- ВЫ ЗАКЛЮЧЕНЫ В ГРАНИЦАХ СВОЕЙ "ОШИБОЧНОЙ УВЕРЕННОСТИ"
- VC8 - "божественная граница", расположена в центре пупка.
- ВОЛЬНАЯ РУССКАЯ ПРЕССА ЗА ГРАНИЦЕЙ. «ПОЛЯРНАЯ ЗВЕЗДА» И «КОЛОКОЛ» А.И. ГЕРЦЕНА