АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Свойства асимптотических функций

Читайте также:
  1. III. Психические свойства личности – типичные для данного человека особенности его психики, особенности реализации его психических процессов.
  2. Ms Excel: мастер функций. Логические функции.
  3. V2: Электрические и магнитные свойства вещества
  4. Автоматизация функций в социальной работе
  5. Акустические свойства голоса
  6. Акустические свойства строительных материалов
  7. Алгебраические свойства векторного произведения
  8. АЛГОРИТМ И ЕГО СВОЙСТВА
  9. Алгоритм построения графиков функций вида
  10. Аллювиальные отложения и их свойства
  11. АНАЛИЗ ФУНКЦИЙ СПЕЦИАЛИСТОВ ПО СТРАТЕГИЧЕСКОМУ МЕНЕДЖМЕНТУ И ПОЛНОМОЧИЙ ОРГАНОВ УПРАВЛЕНИЯ ОРГАНИЗАЦИИ, ПРИНИМАЮЩИХ СТРАТЕГИЧЕСКИЕ РЕШЕНИЯ.
  12. Анализ функций управления

Введённые нами определения обладают некоторыми свойствами транзитивности, рефлексивности и симметричности.

Транзитивность:

и влечёт ;

и влечёт ;

и влечёт ;

и влечёт ;

и влечёт .

Рефлексивность:

, , .

Симметричность:

если и только если .

Обращение:

если и только если ;

если и только если .

 

Можно провести весьма условную параллель: отношения между функциями f и g подобны отношениям между числами a и b:

 

 

Замечание. Следует осторожно использовать формулы при работе с О -символикой. Например, формулу ошибочно трактовать по правилу суммы

,

т.к. число последовательных фрагментов есть сама функция от n.

Если операция выполняется за фиксированное число шагов, не зависящее от количества данных, то принято писать O (1).

Пример 1: пусть мы смогли определить величины T (0) = 1, Т (1) = 4, Т (2) = 9 или в общем случае T (n) = (n + 1)². Требуется найти асимптотическую оценку О (f (n)), т.е. некоторую функцию вида f (n), которая бы относилась к одному из известных классов сложности алгоритмов и график которой располагался бы над графиком функции экспериментальных значений времени выполнения программы T (n), то есть описывал зависимость числа выполненных инструкций в худшем случае.

Решение: Как известно, (n + 1)2 = n 2 + 2 n + 1, то есть T (n) = n 2 + 2 n + 1.

В качестве асимптотической оценки, т.е. функции расположенной над T (n) можно взять функцию вида f’ (n) = n 3, так как n 3 > n 2 + 2 n + 1, однако тем самым мы ухудшим «мнение» эксперта об исследуемом алгоритме (он работает быстрее), так как если положить f (n) = n 2, и найти такую константу с, чтобы выполнилось T (n) ≤ n 2 * с. При с = 2, начиная с n0 = 3, исключая случаи запуска программы с длиной входных данных 1 и 2. Разрешая неравенство 2 n 2 ≥ n2 + 2 n + 1 относительно n, получаем n0 = 3. Рис. 4 Определение константы с и n0  

Заметим, что при с = 3 → n0 = 2, что лучше чем при с = 3, так как асимптотическая оценка справедлива на большем диапазоне входных данных. Самый «идеальный» случай, когда функция f (n) превышает T (n) на всем наборе исходных данных n ≥ 1 – это условие выполняется при с = 4 и n0 = 1.

В отличие от примера T (n) как функцию от некоторого аргумента аналитически задать сложно, а в большинстве случаев – невозможно. Единственный выход – найти верхнюю и нижнюю асимптотическую оценку характера изменения T (n). Для чего вводиться функция Ω(f (n)), которая представляет нижнюю асимптотику. Тогда надо подобрать такой вид функции роста (то есть полином f (n)) для О(f (n)) и Ω(f (n)), что они совпадут в обоих случаях с точностью до полинома – тогда получим точную асимптотическую оценку Θ(f (n))функции T (n). Согласно определению Θ(×)

.

Не трудно заметить, что условие

выполняется при с 1 = 1 и с 2 = 4 на всем множестве n. Поэтому для полинома точная асимптотическая оценка составляет n 2.

Поскольку для f (n) = n 3 имеет строгое неравенство n 3 > n 2 + 2 n + 1, то f (n) = n 3 есть o (×), то есть о(T (n)) = n 3.

 

Пример 2. По экспериментальным данным T(n) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ (n), O(n), o(n), W (n), ω (n):

n                              
T (n)                              

 

Решение. Будем решать поставленную задачу графическим методом, то есть построив график T (n), будем подбирать функции, описывающие соответствующий класс сложности алгоритмов. Построив соответствующие графики, наглядно покажем выполнения требований, согласно определениям Θ (n), O(n), o(n), W (n), ω (n).

Рис. 5 Графическое и табличное представления решения задачи.

Как видно из графиков, наилучшим приближением к экспериментальным значениям T (n) будет функция роста, описываемая полиномом вида . Действительно, согласно определению Θ(n) необходимо выполнение требования и при , и условие выполняется (на графике через c 1 f (n) и c 2 f (n) обозначены асимптотические границы согласно определению Θ (n) и рис. 2.). Поэтому можно утверждать, что .

Графики и таблица подтверждают, что

при и ;

при и ;

при и ;

при и .


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)