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

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

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

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

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

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

ТЕМА НОМЕРА: «Большая восьмерка» большого пестрого дятла

Из книги Журнал «Компьютерра» N 27-28 от 25 июля 2006 года автора Журнал «Компьютерра»

ТЕМА НОМЕРА: «Большая восьмерка» большого пестрого дятла Автор: Леонид Левкович-МаслюкЕсть детские вопросы, которые не оставляют человека всю жизнь, - и я постепенно прихожу к выводу, что они-то и есть единственно важные и интересные. О чем разговаривают животные - один из


Множество (Set)

Из книги Руководство по стандартной библиотеке шаблонов (STL) автора Ли Менг

Множество (Set) set - это ассоциативный контейнер, который поддерживает уникальные ключи (не содержит ключи с одинаковыми значениями) и обеспечивает быстрый поиск ключей.template ‹class Key, class Compare = less‹Key›, template ‹class U› class Allocator = allocator›class set {public: // typedefs: typedef Key key_type; typedef Key


Множество с дубликатами (Multiset)

Из книги 200 лучших программ для Интернета. Популярный самоучитель автора Краинский И

Множество с дубликатами (Multiset) multiset - это ассоциативный контейнер, который поддерживает равные ключи (возможно, содержит множественные копии того же самого значения ключа) и обеспечивает быстрый поиск ключей.template ‹class Key, class Compare = less‹Key›, template ‹class U› class Allocator = allocator›class


Программы для пересылки файлов большого размера

Из книги Основы объектно-ориентированного программирования автора Мейер Бертран

Программы для пересылки файлов большого размера Пересылка по электронной почте файлов большого размера всегда сопряжена с проблемами. Во-первых, размер почтового ящика получателя может быть недостаточно велик для получаемого файла. Во-вторых, отправка больших файлов


У11.11 Модуль "множество"

Из книги TCP/IP Архитектура, протоколы, реализация (включая IP версии 6 и IP Security) автора Фейт Сидни М

У11.11 Модуль "множество" Напишите класс, реализующий множество элементов произвольного типа со стандартными операциями: проверка принадлежности, добавление нового элемента, объединение, пересечение и другими. Не забудьте включить подходящие утверждения. Приемлема любая


5.25 Множество адресов для одного интерфейса

Из книги Программирование на языке Ruby [Идеология языка, теория и практика применения] автора Фултон Хэл

5.25 Множество адресов для одного интерфейса Некоторые производители маршрутизаторов предусматривают возможность присваивать несколько IP-адресов одному интерфейсу маршрутизатора. Для чего же это нужно? Несколько адресов подсетей могут потребоваться, во-первых, в


Множество узлов (node-set)

Из книги Firebird РУКОВОДСТВО РАЗРАБОТЧИКА БАЗ ДАННЫХ автора Борри Хелен

Множество узлов (node-set) Несмотря на то, что XSLT оперирует логической моделью XML-документа как деревом с узлами, в XSLT нет типа данных, который соответствовал бы одному узлу. Вместо этого используется гораздо более мощный и гибкий тип данных, называемый множеством узлов (англ.


Множество пользователей и параллельность

Из книги Как раскрутить и разрекламировать Web-сайт в сети Интернет автора Загуменов Александр Петрович

Множество пользователей и параллельность СУБД разработана для того, чтобы обеспечить работу множества пользователей с образами хранимых данных и, чтобы можно было использовать изменяющие запросы, которые могут влиять на работу других пользователей. В этой ситуации


Множество привилегий и множество получателей привилегий

Из книги Новый ум короля [О компьютерах, мышлении и законах физики] автора Пенроуз Роджер

Множество привилегий и множество получателей привилегий Есть возможность предоставлять несколько привилегий в одном операторе и предоставлять одну или более привилегий множеству пользователей или объектов.Множество привилегийДля предоставления получателю


Глава 1 Этапы большого пути

Из книги UNIX: разработка сетевых приложений автора Стивенс Уильям Ричард

Глава 1 Этапы большого пути Хороший web-сайт – это не просто набор страниц, связанных гиперссылками, и далеко не только то, что видит пользователь на экране монитора. Его внутреннее устройство довольно сложно. Ведь требуется обеспечить максимум удобств, как для


Эффект наличия слишком большого количества дочерних процессов

Из книги Вопросы истории: UNIX, Linux, BSD и другие автора Федорчук Алексей Викторович

Эффект наличия слишком большого количества дочерних процессов В табл. 30.1 (строка 2) указано время (1,8 с), затрачиваемое центральным процессором в случае наличия 15 дочерних процессов, обслуживающих не более 10 клиентов. Мы можем оценить эффект «общей побудки», увеличивая


Эффект наличия слишком большого количества дочерних процессов

Из книги автора

Эффект наличия слишком большого количества дочерних процессов Мы можем проверить, возникает ли в данной версии сервера эффект «общей побудки», рассмотренный в предыдущем разделе. Как и раньше, время работы ухудшается пропорционально числу избыточных дочерних