КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Примеры использования
Асимптотические обозначения в уравнениях Другие Перестановочная симметрия Симметричность Рефлексивность Транзитивность Основные свойства Другие подобные обозначения Для функций f(n) и g(n) при n → n 0 используются следующие обозначения:
где U — проколотая окрестность точки n 0. · · f (n) = Θ(f (n)) · f (n) = O (f (n)) · f (n) = Ω(f (n)) ·
· o (f) = const × o (f); O (f) = const × O (f); · o (f) = o (const × f); O (f) = O (const × f); · o (f) = O (f); · o (f) + o (f) = o (f); o (f) + O (f) = O (f); O (f) + O (f) = O (f); · O (f) × O (g) = O (fg); o (f) × O (g) = o (fg); o (f) × o (g) = o (fg); · O (O (f)) = O (f); · o (o (f)), o (O (f)), O (o (f)) = o (f); · O (- f) = O (f) · Если в правой части уравнения находится только асимптотическое обозначение (например n = O (n ²)), то знак равенства обозначает принадлежность множеству (n ∈ O (n ²)). · Если в уравнении асимптотические обозначения встречается в другой ситуации, они рассматриваются как подставляемые взамен их некоторые функции. Например, при x → 0 формула ex − 1 = x + o (x) обозначает, что ex − 1 = x + f (x), где f (x) — функция, о которой известно только то, что она принадлежит множеству o (x). Предполагается, что таких функций в выражении столько, сколько раз встречаются в нём асимптотические обозначения. Например, — содержит только одну функцию из класса O (n 2). · Если асимптотические обозначения встречаются в левой части уравнения, используют следующее правило: · Несколько таких уравнений могут быть объединены в цепочки. Каждое из уравнений в таком случае следует интерпретировать в соответствии с предыдущим правилом. Приведенная интерпретация подразумевает выполнение соотношения: , где A, B, C — выражения, которые могут содержать асимптотические обозначения. · ex = 1 + x + x ²/2 + O (x ³) при x → 0. · n! = O ((n / e) n +1/2) при n → ∞. · T (n) = (n + 1)2 = O (n 2) при n → ∞. Доказательство: Если положить n 0 = 1 и c = 4, то для n ≥1 будет выполняться неравенство (n + 1)2 < 4 n 2. Отметим, что нельзя положить n 0 = 0, так как T (0) = 1 и, следовательно, это значение при любой константе c больше c 02 = 0. · Функция T (n) = 3 n 3 + 2 n 2 при n → ∞ имеет степень роста O (n 3). Чтобы это показать, надо положить n 0 = 0 и c = 5. Можно, конечно, сказать, что T (n) имеет порядок O (n 4), но это более слабое утверждение, чем то, что T (n) имеет порядок роста O (n 3). · Докажем, что функция 3 n при n → ∞ не может иметь порядок O (2 n). Предположим, что существуют константы c и n 0 такие, что для всех n ≥ n 0 выполняется неравенство 3 n ≤ c 2n. Тогда c ≥ (3/2)n для всех n ≥ n 0. Но (3/2)n принимает любое, как угодно большое, значение при достаточно большом n, поэтому не существует такой константы c, которая могла бы мажорировать (3/2)n для всех n больших некоторого n 0. · T (n) = n 3 + 2 n 2 есть Ω(n 3) при n → ∞. Для проверки достаточно положить c = 1. Тогда T (n) > cn 3 для n = 0,1,....
Дата добавления: 2014-01-15; Просмотров: 422; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |