САОД Методы анализа, страница 3
Описание файла
Документ из архива "САОД Методы анализа", который расположен в категории "". Всё это находится в предмете "введение в специальность" из 1 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "введение в специальность" в общих файлах.
Онлайн просмотр документа "САОД Методы анализа"
Текст 3 страницы из документа "САОД Методы анализа"
(а) 
(б) 
Рис. 3. Верхняя (а) и нижняя (б) асимптотические оценки функции 
Асимптотические обозначения 
могут употребляются внутри формул. Например, мы можем написать выражение
имея в виду сумму h(1) + h(2) + … + h(n), где h() – некоторая функция, для которой h(i) = O(i). Можно показать, что сама эта сумма как функция от n есть O(n2).
1.3.3![]()
и ![]()
обозначения
Запись 
означает, что с ростом n отношение 
остаётся ограниченным. Если к тому же
,
то мы пишем 
(читается «эф от эн есть о малое от же от эн»). Формально говоря, , если для всякого положительного 
найдётся такое n0, что 
при всех 
. Тем самым запись предполагает, что 
и 
неотрицательны для достаточно больших n.
Пример: 
но 
Аналогичным образом вводится 
обозначение: говорят, что есть 
(«эф от эн есть омега малая от же от эн»), если для всякого положительного найдется такое n0, что 
при всех , причем
.
Очевидно, 
равносильно 
Пример: 
, но 
Таким образом, может существовать три основных случая (существует и четвертый случай, когда предела не существует, однако он встречается довольно редко в реальной практике анализа алгоритмов):
Однако на практике строгими определениями пользуются редко. Существует более удобный метод выполнения этой оценки, основанный на мощном математическом аппарате, специально созданного для вычисления пределов отношения двух рассматриваемых функций, в частности правилом Лопиталя (L'Hopital):
и формулой Стирлинга (Stirling) для достаточно больших n:
.
Пример 1. Сравните порядки роста функций f(n)=n(n – 1)/2 и g(n)=n2.
Решение: поскольку
предел равен положительной константе, обе функции имеют одинаковый порядок роста, что записывается как 
.
Пример 2. Сравните порядки роста функций 
и 
.
Решение:
.
Поскольку предел равен нулю, функция имеет меньший порядок роста, чем . То есть 
.
Пример 3. Сравните порядки роста функций 
и 
.
Решение: воспользовавшись формулой Стерлинга, получим:
Следовательно, хотя функция 
растет очень быстро, функция растет еще быстрее, что записывается как 
. Обратим внимание, что при использовании этой формы записи, в отличие от случая использования пределов, не можем сделать однозначный вывод о том, что порядок роста функции выше, чем функции , а не, скажем, равен ей, поэтому используется «большая» омега.
1.3.4Свойства асимптотических функций
Введённые нами определения обладают некоторыми свойствами транзитивности, рефлексивности и симметричности.
Транзитивность:
и 
влечёт 
;
и 
влечёт 
;
и 
влечёт 
;
и 
влечёт 
;
и 
влечёт 
.
Рефлексивность:
, 
, 
.
Симметричность:
если и только если 
.
Обращение:
если и только если 
;
если и только если 
.
Можно провести весьма условную параллель: отношения между функциями 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 = n2 + 2n + 1, то есть T(n) = n2 + 2n + 1.
| В качестве асимптотической оценки, т.е. функции расположенной над T(n) можно взять функцию вида f’(n) = n3, так как n3 > n2 + 2n + 1, однако тем самым мы ухудшим «мнение» эксперта об исследуемом алгоритме (он работает быстрее), так как если положить f(n) = n2, и найти такую константу с, чтобы выполнилось T(n) ≤ n2 * с. При с = 2, начиная с n0 = 3, исключая случаи запуска программы с длиной входных данных 1 и 2. Разрешая неравенство 2n2 ≥ n2 + 2n + 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. Поэтому для полинома 
точная асимптотическая оценка составляет n2.
Поскольку для f(n) = n3 имеет строгое неравенство n3 > n2 + 2n + 1, то f(n) = n3 есть o(), то есть о(T(n)) = n3.
Пример 2. По экспериментальным данным T(n) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(n), O(n), o(n), (n), ω(n):
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 20 | 30 | 50 | 100 | 500 |
| T(n) | 13 | 38 | 93 | 137 | 227 | 297 | 464 | 507 | 636 | 790 | 3476 | 7472 | 18306 | 84060 | 1900163 |
Решение. Будем решать поставленную задачу графическим методом, то есть построив график T(n), будем подбирать функции, описывающие соответствующий класс сложности алгоритмов. Построив соответствующие графики, наглядно покажем выполнения требований, согласно определениям Θ(n), O(n), o(n), (n), ω(n).
Рис. 5 Графическое и табличное представления решения задачи.
Как видно из графиков, наилучшим приближением к экспериментальным значениям T(n) будет функция роста, описываемая полиномом вида 
. Действительно, согласно определению Θ(n) необходимо выполнение требования 
и при 
, 
и 
условие выполняется (на графике через c1f(n) и c2f(n) обозначены асимптотические границы согласно определению Θ(n) и рис. 2.). Поэтому можно утверждать, что 
.
Графики и таблица подтверждают, что
при 
и 
;
при 
и 
;
при 
и ;
при 
и .
1.3.5Сложение и умножение в O-символике
Правило суммы. Если 
и 
, то 
. (Аналогичные утверждения справедливы также для множеств 
и 
).
Доказательство. (Доказательство этой теоремы основывается простом соотношении для произвольных вещественных чисел 
, 
,
,
: если 
и 
, то 
)
Поскольку 
, существует константа с1 и неотрицательное целое число n1 такие, что для всех 
справедливо 
.
По аналогии, поскольку 
существует константа 
и неотрицательное целое число 
такие, что для всех 
справедливо 
.
Обозначим через 
и рассмотрим случай, когда верны оба неравенства для случая 
. Сложив приведенные выше неравенства, получим
.
Откуда следует, что . Исходя из определения О-асимптотики, в качестве констант с и 
положим 
и 
.
При анализе алгоритмов теорема о сумме используется следующим образом. Пусть имеются два фрагмента программы P2 и P2, причем время выполнения одного 
, а другого 
. Очевидно, что если эти фрагменты выполняются последовательно, то общее время работы (общая трудоемкость последовательно выполняемых фрагментов) будет равно 
. Тогда асимптотическая оценка всего фрагмента по теореме о сумме – 
. Это означает, что общая эффективность алгоритма зависит от той части, для которой функция роста трудоемкости имеет наибольший порядок роста, т.е. от наименее эффективной его части алгоритма:
