Лекция 1.3 (АсимптСложн). Структуры и алгоритмы обработки данных Асимптотический метод оценки (окончание)

• Название: Структуры и алгоритмы обработки данных Асимптотический метод оценки (окончание)
• Дата: 28.03.2022
• Размер: 1.34 Mb.
• Имя файла: Лекция 1.3 (АсимптСложн).pptx
• Тип: Документы; #421316

Структуры и алгоритмы обработки данных

5. Асимптотический метод оценки (окончание).

Рысин М.Л.

5. Асимптотический метод оценки

Виды асимптотических обозначений

-обозначение асимптотической оценки

Для некоторой функции g(n) запись f(n) = (g(n)) обозначает множество функций:
(g(n)) = {f (n): существуют положительные константы c1, c2, такие что 0  с1g(n)  f(n)  c2 g(n)

для всех n > nо}

Функция f(n) принадлежит множеству (g(n)), если существуют константы с1>0 и с2>0, позволяющие заключить эту функцию в рамки между с1g(n) и с2g(n) для достаточно больших n (> nо).

-нотация для оценки сложности алгоритма

Т.о. в -обозначениях функция f(n) асимптотически ограничивается сверху и снизу:

для всех n>nо f(n) = g(n) с точностью до постоянного множителя

Т.е. g(n) – это аппроксимация для функции роста T(n)
Тогда g(n) является:

1) асимптотически точной оценкой функции Т(n) и

2) используется для оценки сложности алгоритма с функцией роста T(n) в худшем, лучшем и среднем случае.

Пример

Доказать, что асимптотическая оценка функции T(n)=0,5*n2 – 3*n есть θ(n2) или T(n)= θ(n2).

Для этого определим константы c1, c2 и n0, для которых справедливо:

c1*n2 ≤ 0,5*n2 – 3*n ≤ c2*n2 для всех n ≥ n0.

Разделив неравенство на n2, получим:

c1 ≤ 0,5 – 3/n ≤ c2.

Правая часть 0,5 – 3/n ≤ c2 выполнится для всех n ≥ 1, если выбрать c2 ≥ 0.5 (при n→∞ 3/n→0)
Аналогично левая часть c1 ≤ 0,5 – 3/n выполнится для всех n ≥ 7, если выбрать c1 ≤ 1/14 (0,5-3/7=1/14)
Тогда найдены c1 = 1/14, c2 = 0.5 и n0=7, а, значит, по определению, T(n)= θ(n2), ч.т.д.
Константы можно выбрать и по-другому, но важны не сами константы, а то, что они существуют.

О-обозначение асимптотической оценки

Используют, если достаточно определить только асимптотическую верхнюю границу
f(n)=O(g(n)) означает множество функций {f(n) таких, что : существуют положительная константа с и n0 такие, что 0 ≤ f(n) ≤ c*g(n) для всех n ≥ n0}
Запись f(n) = О(g(n)) обозначает принадлежность f(n) множеству О(g(n))
О-обозначения применяются, когда нужно указать верхнюю границу функции роста с точностью до постоянного множителя с
Т.е. для всех n>nо функция f(n) не превышает значения функции g(n) с точностью до постоянного множителя
Из f(n) = (g(n)) следует f(n) = O(g(n)), т.к. -обозначения более сильные, чем О-обозначения: (g(n)) O(g(n)).

О-нотация для оценки сложности алгоритма

Т.к. T(n) – это функция, то она принадлежит некоторому множеству функций
Для аппроксимации (приближения) T(n) подбирается простая g(n) и константа С, так, что С·g(n) превышает T(n), по мере того как n значительно растет
Для больших n поведение T(n) ограничивается С·g(n)
T(n) имеет порядок роста O(g(n)), если имеется константа с и счетчик n0, такие что 0 < T(n) ≤ с·g(n), для n>=n0.
Границы сверху достаточно для оценки сложности алгоритма в худшем случае.

Ω-обозначение асимптотической оценки

Для данной функции g(n) выражение f(n)=Ω(g(n)) обозначает множество функций {f(n): таких, что существуют константа с>0 и n0, для которых 0 < c·g(n) ≤ f(n) для всех n≥n0}
Т.е. для всех n, лежащих справа от n0, значения функции f(n) ≥ c·g(n)
Суть Ω нотации: существует константа с такая, что для бесконечного числа значений n>n0 выполняется неравенство T(n) ≥ c·g(n). →

Ω-нотация для оценки сложности

В Ω - обозначениях функции роста даётся её асимптотическая нижняя граница с точностью до постоянного множителя
Нижней границы достаточно для оценки времени работы алгоритма в наилучшем случае
Например, время работы алгоритма сортировки вставкой находится в пределах между Ω(n) и О(n2), асимптотически точную оценку для этого алгоритма получить сложно.

Асимптотически точная оценка сложности алгоритма

Теорема. Для любых двух функций f(n) и g(n) соотношение f(n) = (g(n)) выполняется тогда и только тогда, когда f(n) = O(g(n)) и f(n) = (g(n))
Доказательство непосредственно вытекает из приведенных определений
На практике теорема применяется для определения асимптотически точной оценки с помощью асимптотических верхней и нижней границ
Пример: если а>0, b и с — константы, то из соотношений аn2 + bn + с = О (n2) и аn2 + bn + с = (n2) непосредственно следует, что аn2 + bn + с = (n2).

Нотации в уравнениях и неравенствах (1/2)

Как интерпретируются формулы типа Т(n)=О(n2) и 2n2+Зn+1=2n2+(n)?
Если в правой части формулы находится только асимптотическое обозначение (Т(n)=О(n2)), то знак равенства используется для указания принадлежности множеству: Т(n)О(n2)
В другой ситуации они рассматриваются как подставляемые взамен некоторой функции, имя которой не имеет значения
Пример: 2n2+3n+1=2n2+(n) означает, что 2n2+3n+1=2n2+f(n), где f(n) —функция из множества (n)
Здесь f(n) =Зn +1, и она принадлежит множеству (n)
Например, время работы алгоритма сортировки методом слияния в наихудшем случае было выражено в виде рекуррентного уравнения:

Т(n) = 2Т (n/2) + (n)

Если интересует только асимптотическое поведение Т(n), то нет смысла точно выписывать все слагаемые низших порядков, подразумевается, что все они включены в безымянную функцию, обозначаемую (n).

Нотации в уравнениях и неравенствах (2/2)

Если асимптотические обозначения появляются в левой части уравнения, например, 2n2+(n)=(n2)
То уравнения интерпретируются в соответствии с правилом:
При любом выборе безымянных функций, подставляемых вместо асимптотических обозначений в левую часть уравнения, можно выбрать и подставить в правую часть такие безымянные функции, что уравнение будет правильным.
В примере: для любой функции f(n)  (n) существует некоторая функция g(n) (n2), такая что 2n2+ f(n)=g(n2) для всех n
Т.е. правая часть уравнения предоставляет меньший уровень детализации, чем левая.

о-обозначение (1/2)

Верхняя О-граница может описывать асимптотическое поведение функции с разной точностью
Так, если граница 2n2 = О(n2) дает точное представление об асимптотическом поведении функции, то граница2n2 = о(n3) гораздо менее точна
Если верхняя граница не является асимптотически точной оценкой функции, то применяются о-обозначения
Формальное определение множества о(g(n)):

o(g(n)) = {f(n) : для любой константыс>0 существует n0>0 такое, что 0f(n)c(g(n)) для всех nn0 }

Определения О-обозначений и о-обозначений похожи. →

о-обозначение (2/2)

Отличие – определение f(n)=О(g(n)) ограничивает функцию f(n) неравенством 0f(n)сg(n) лишь для некоторой константы с>0, а определение f(n) = о(g(n)) ограничивает её неравенством 0  f(n) < сg(n) для любой константы с>0
Интуитивно понятно, что в о-обозначениях, если n стремится к бесконечности, то f(n) пренебрежимо мала по сравнению с функцией g(n), т.е.
Например, 2n=о(n2), но 2n2о(n).

-обозначение (1/2)

По аналогии, -обозначения соотносятся с -обозначениями так же, как о‑обозначения с О-обозначениями
‑обозначениями указывается нижний предел, не являющийся асимптотически точной оценкой
Один из возможных способов определения для -обозначения:

f(n) = (g(n)) тогда и только тогда, когда g(n) = о(f(n))

-обозначение (2/2)

Формально, (g(n)) («омега малое от g от n») определяется как множество  (g (n)) = {f (n): для любой положительной константы с существует n0>0, такое что 0сg(n)для всех n> n0}
Например, n2/2 = (n), но n2/2(n2).
Соотношение f(n)= (g(n)) подразумевает, что

если этот предел существует.

Функция f(n) становится сколь угодно большой по сравнению с функцией g(n), если n стремится к бесконечности.

Свойства асимптотических сравнений

Использование асимптотических оценок

Классы сложности алгоритмов:

f(n) = O(1) константа
f(n) = O(log(n)) логарифмический рост
f(n) = O(n) линейный рост
f(n) = O(n·log(n)) квазилинейный рост
f(n) = O(nm) полиномиальный рост
f(n) = O(2n) экспоненциальный рост.

Применение типовых функций для оценки сложности алгоритмов

Правила вычисления асимптотических оценок

Пусть f, g – функции, k – константа. Тогда:
O(k * f) = O(f) – постоянные множители не имеют значения при определения порядка сложности;
O(f * g) = O(f) * O(g) или O(f / g) = O(f) / O(g) – порядок сложности произведения двух функций равен произведению их сложностей;
O(f + g) = max(O(f) и O(g)) – порядок сложности суммы двух функций определяется как порядок доминанты первого и второго слагаемых (из суммы двух функций выбирается лишь одна с наибольшим порядком сложности).
Примеры:

1. O(1,5n) = O(n)

2. O(17*n*n) = O(17n) * O(n) = O(n) * O(n) = O(n*n) = O(n2)

3. O(n5 + n2) = O(n5).

Основание логарифма при определении порядка роста

Основание логарифма при оценке сложности можно не указывать

Доказательство:

Пусть есть log2 n
Тогда log2 n = log3 n/log32, т.е. О(log2 n) = О(log3 n), что справедливо и для любого другого основания (log32 как константа не учитывается).

Время выполнения алгоритма

1. Время вычисления любого выражения, оператора присваивания – О(1)

2. Время выполнения блока определяется по правилу суммы

3. Время условных операторов состоит из:

времени выполнения логического выражения – О(1)
максимального времени веток then или else, например:

Пусть время блока then имеет порядок О(n), а блок else O(n2),
Тогда оператор if имеет порядок О(1) + max(О(n), O(n2)) = O(n2).


4. Время выполнения цикла равно сумме времени всех итераций цикла:


Каждая итерация равна сумме времени выполнения тела цикла и времени вычисления условия цикла (+1).
Время проверки условия цикла равно, как правило, O(1).

Примеры вычисления

Пример 1:

x=0;

for (int i=0;i< 500;i++)

x=x+i;

Ответ: Т(n) = Т(1+501+501+500) = О(1), т.к. не зависит от n – количества входных данных.

Пример 2:

while (n>1) { n=n/2; }

Решение:

Т(n) равно количеству делений
Если n – это степень 2, и n = 1 на k-ом шаге, то чтобы найти k (сколько раз отработал цикл), из n=2k → k= log2 n

Ответ: T(n) = О(log n).

Интеллектуальная сложность алгоритма

Внешние меры эффективности:

Вычислительная сложность
Пространственная (емкостная) сложность

Внутреннее качество:

Интеллектуальная сложность – определяет сложность разработки и понятность алгоритма

Все виды сложности обычно взаимосвязаны.

6. Алгоритмы внутренних сортировок.