Главная » Ядро Linux » Множество большого-тета

0

Когда  говорят об  обозначении большого-О,  то  чаще  всего  имеют  в виду  то, что Дональд Кнут   (Donald  Knulh)  описывал с  помощью обозначения  "большого-тета". Обозначение "болыпого-О" соответствует верхней границе. Например,  число  7 — это верхняя граница числа  6, кроме  того, числа  9, 12 и  65— это  тоже  верхние границы числа  6. Когда  рассматривают рост  функции, то обычно наиболее интересна наименьшая верхняя  граница или  функция,  которая моделирует как  верхнюю, так  и  нижнюю границу’.  Профессо р  Кнут  описывает это  с  помощью обозначения  большого-тета следующим образом.

Если    f (х)    принадлежит  множеству  большого-тета  от   g (x) ,   то g(х)    являетс я  одновременно  и  верхней и  нижней  границей  f(х )

Можно также  сказать, что  функция f (x)   порядка  функции g (х) .  Порядок, или множество  "большого-тета" алгоритма, — один  из  наиболее важных  математических инструментов изучения алгоритмов.

Следовательно, когда  говорят об  обозначении большого-О,  то  чаще  всего  имеют в  виду  наименьший  возможный вариант "большого-О" — "болыное-тета". Об  этом  не нужно   особо  волноваться, если, конечно,  нет  желания доставить удовольствие профессору Кнуту.

1 Если интересно ,  т о  нижня я  границ а  описываетс я  с  помощь ю  обозначени я  большого-омега . Определени е аналогичн о определени ю множества большого-О,  за исключением того,  чт о значени я функции  g(s )  должны  быт ь меньше  значений функции   f (х)  или  равны  им.

Источник: Лав,  Роберт. Разработка ядра  Linux, 2-е  издание. : Пер.  с англ.  — М.  : ООО  «И.Д.  Вильяме» 2006. — 448 с. : ил. — Парал. тит. англ.

По теме:

  • Комментарии