|
||||||||||||||||||||||||||||||||||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[8] заключать, что fi(n) = /2(га)! Определение Q(g(n)) предполагает, что функции /(га) и д(п) асимптотически неотрицательны, т.е. неотрицательны для достаточно больших значений га. Заметим, что если функции fug строго положительны, то можно исключить по из определения (изменив константы с\ и с2 так, чтобы для малых га неравенство также выполнялось). Если /(га) = Q(g(n)), то говорят, что д(п) является асимптотически точной оценкой для /(га). На самом деле это отношение симметрично: если /(га) = Q(g(n)), то д(п) = ©(/(га)). Вернёмся к примеру из главы 1 и проверим, что (1/2)га2 - Зга = ©(га2). Согласно определению, надо указать положительные константы С\,С2 и число по так, чтобы неравенства cira2 -га2 - Зга с2га2 выполнялись для всех га гао- Разделим на га2: 13 2га Видно, что выполнения второго неравенства достаточно положить с2 = 1/2. Первое будет выполнено, если (например) щ = 7 и с\ = 1/14. Другой пример использования формального определения: покажем, что 6га3 ф 0(га2). В самом деле, пусть найдутся такие с2 и по, что 6га3 с2га2 для всех га uq. Но тогда га с2/6 для всех га гао - что явно не так. Отыскивая асимптотически точную оценку для суммы, мы можем отбрасывать члены меньшего порядка, которые при больших га становятся малыми по сравнению с основным слагаемым. Заметим также, что коэффициент при старшем члене роли не играет (он может повлиять только на выбор констант с\ и с2). Например, рассмотрим квадратичную функцию /(га) = an2 + Ьп + с, где а,Ь,с - некоторые константы и а > 0. Отбрасывая члены младших порядков и коэффициент при старшем члене, находим, что /(га) = 0(га2). Чтобы убедиться в этом формально, можно положить с\ = а/4, с2 = 7а/4 и гао = 2 • тах((6/а), -\/с/а) (проверьте, что требования действительно выполнены). Вообще, для любого полинома р(п) степени d с положительным старшим коэффициентом имеем р(га) = 0(rad) (задача 2-1). Упомянем важный частный случай использования 0-обозначений: 0(1) обозначает ограниченную функцию, отделённую от нуля некоторый положительной константой при достаточно больших значениях аргумента. (Из контекста обычно ясно, что именно считается аргументом функции.) О- и -обозначения Запись /(га) = Q(g(n)) включает в себя две оценки: верхнюю и нижнюю. Их можно разделить. Говорят, что /(га) = 0(д(п)), если найдётся такая константа с > 0 и такое число по, что 0 f(n) сд(п) для всех га по Говорят, что /(га) = Q(g(n)), если найдется такая константа с > 0 и такое число щ, что 0 сд(п) f(n) для всех га по. Эти записи читаются так: «эф от эн есть о большое от же от эн», «эф от эн есть омега большая от же от эн». По-прежнему мы предполагаем, что функции fug неотрицательны для достаточно больших значений аргумента. Легко видеть (упр. 2.1-5), что выполнены следующие свойства: Теорема 2.1. Для любых двух функций /(га) и д(п) свойство /(га) = Q(g(n)) выполнено тогда и только тогда, когда /(га) = 0(g(n)) и f(n) = Q(g(n)). Для любых двух функций свойства /(га) = 0(g(n)) и g(n) = £}(f(n)) равносильны. Как мы видели, an2 + Ъп + с = 0(га2) (при положительных а). Поэтому an2 + Ъп + с = 0(п2). Другой пример: при а > 0 можно написать an А-Ь = 0(п2) (положим с = а + 6 и щ = 1). Заметим, что в этом случае an Л-Ь ф Q(n2 и an -\-Ъ ф 0(га2). Асимптотические обозначения (в, О и S7) часто употребляются внутри формул. Например, в главе 1 мы получили рекуррентное соотношение Т(п) = 2Г(га/2) + 6(га) для времени работы сортировки слиянием. Здесь О(га) обозначает некоторую функцию, про которую нам важно знать лишь, что она не меньше с\п и не больше сп для некоторых положительных с\ и С2 и для всех достаточно больших п. Часто асимптотические обозначения употребляются не вполне формально, хотя их подразумеваемый смысл обычно ясен из контекста. Например, мы можем написать выражение п 8 = 1 имея в виду сумму h(l) + h(2) + ... + h(n), где h(i) - некоторая функция, для которой h(i) = O(i). Легко видеть, что сама эта сумма как функция от п есть 0(п2). Типичный пример использования асимптотических обозначений - цепочка равенств наподобие 2га2 + Зга + 1 = 2га2 + О(га) = 0(га2). Второе из этих равенств (2га2 + О(га) = 0(га2)) понимается при этом так: какова бы ни была функция h(n) = О(га) в левой части, сумма 2га2 + h(n) есть 0(га2). о- и а>обозначения Запись /(га) = 0(д(п)) означает, что с ростом га отношение f(n)/g(n) остаётся ограниченным. Если к тому же lim М = 0,(2.1) га-»схэ д(п) то мы пишем /(га) = о(д(п)) (читается «эф от эн есть о малое от же от эн»). Формально говоря, /(га) = о(д(п)), если для всякого положительного е > 0 найдётся такое гао, что 0 f(n) £д(п) при всех га по. (Тем самым запись /(га) = о(д(п)) предполагает, что /(га) и д(п) неотрицательны для достаточно больших га.) Пример: 2га = о(га2), но 2га2 ф о(га2). Аналогичным образом вводится -обозначение: говорят, что /(га) есть uj(g(n)) («эф от эн есть омега малая от же от эн»), если для любого положительного с существует такое гао, что 0 сд(п) f(n) при всех га гао- Другими словами, /(га) = uj(g(n)) означает, что д(п) = о(/(га)). Пример: га2/2 = oj(n), но га2/2 ф uj(n2). Сравнение функций Введённые нами определения обладают некоторыми свойствами транзитивности, рефлексивности и симметричности: Транзитивность:
Рефлексивность: /(га) = в(Дга)), /(га) = О(Дга)), /(га) = Щ/(п)). Симметричность: /(га) = Q(g(n)) если и только если д(га) = в(/(га)). Обращение: /(га) = 0(д(п)) если и только если д(п) = i7(/(ra)), /(га) = о(д(п)) если и только если д(п) = uj(f(n)). Можно провести такую параллель: отношения между функциями fug подобны отношениям между числами а и Ь:
|
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||||||||||||||||||||||||||||||||||||||||||||||||||