Множество большого-тета

Множество большого-тета

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

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

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

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