Временная сложность

Временная сложность

Временная сложность представляет собой асимптотически время, которое алгоритм найти решение.

Пусть P — проблема, а M — метод решения этой проблемы. Алгоритм представляет собой описание со структурами управления и данных, позволяющее написать метод М на языке, распознаваемом любым человеком или машиной.

Напомню, что управляющими структурами являются: последовательность, разветвление (или выбор), цикл (или итерация). Структуры данных: константы, переменные, массивы (или упорядоченное пространство для хранения), рекурсивные структуры (списки, графики и т. д.).

Основная операция

Сложность состоит в оценке эффективности метода М и в сравнении последнего с другим методом М'. Это сравнение не зависит от среды (машина, система, компилятор, язык и т. д.). Эффективность зависит от количества элементарных операций. Они зависят от размера данных и характера данных.

Пусть n — размер данных, а T(n) — количество элементарных операций. Оценка эффективности будет производиться в лучшем случае, худшем случае и среднем случае.

В случае структуры последовательного типа оценка равна сумме затрат. Например, если алгоритм имеет обработку T1(n), за которой следует T2(n), то T(n)=T1(n)+T2(n).

В случае ответвления оценка равна максимуму ответвлений. Например, алгоритм выполняет T1(n), иначе T2(n), тогда T(n)=max(T1(n), T2(n)).

В случае цикла оценка равна сумме затрат на последовательные проходы. Например, если алгоритм представляет собой время Ti(n) со сложностью Ti(n) в зависимости от номера i итерации. Тогда сложность равна T(n) = sum(i=1 to n) Ti(n).

Для рекурсивной версии я приглашаю вас перейти на соответствующую страницу. Пусть C(n) — обработка, выполняемая в функции «разделяй и властвуй». Тогда сложность равна T(n)=2*T(n/2)+C(n) = n log(n), если C(n)=n.

Обозначение Ландау

Обозначения Ландау характеризуют асимптотическое поведение функции, т. е. поведение f(n) при стремлении n к бесконечности.

Мы говорим, что f(n) является большим O для g(n), если \существует k>0, \существует n_0 \; \для всех n>n_0 \; |ф(п)| \leq |g(n)|\cdot k .

Алгоритм записи Big O Landau с временной сложностью

Алгоритм записи Big O Landau с временной сложностью

Примеры

Алгоритм записи Big O Landau с временной сложностью

Алгоритм записи Big O Landau с временной сложностью

Алгоритм записи Big O Landau с временной сложностью

Худший, лучший и средний

Мы можем вычислить для большинства алгоритмов сложность в худшем случае (наибольшее количество элементарных операций), в лучшем и в среднем. Среднее значение представляет собой сумму, взвешенную по вероятности наличия возможных сложностей. Чаще всего мы используем наихудшую сложность, потому что хотим знать верхнюю границу времени выполнения.

Рассмотрим алгоритм поиска элемента в массиве в итеративной форме. Алгоритм останавливается, когда значение найдено. Алгоритм распадается следующим образом: присваивание 0 i, пока i не прошел всю таблицу, единица увеличивает i, если tab[i]=value, возвращается true, если не в конце таблицы, возвращается false. Пусть C — сложность тела цикла.

В худшем случае алгоритм проходит весь массив, т.е. T(n)=1+n*C=O(n). В лучшем случае элемент находится в начале массива, поэтому T(n)=1+C=O(1). Считаем, что в среднем есть шанс 50%, что элемента нет в массиве, и 50%, что он находится на середине массива (это конечно абсурд, но мы не будем делать все возможности). В этом случае средняя сложность равна T(n)=0,5*(1+n*C)+0,5*(1+n*C/2)=a*n+b с константами a и b = O (не) . Заметим, что асимптотика в среднем такая же, как и в худшем случае.

Примеры

Предположим, что каждое из приведенных ниже выражений дает время обработки T(n), затрачиваемое алгоритмом на решение задачи размера n. Выберите доминирующий термин (члены), имеющий наибольшее увеличение n, и укажите наименьшую сложность Big-Oh для каждого алгоритма.

ВыражениеДоминантныйО(.)
5+0,001n3+0,025n0,001n3Мы3)
500н+100н1.5 + 50нлог10 нет100н1.5Мы1.5)
0,3н+5н1.5 + 2,5 н1.752,5 н1.75Мы1.75)
нет2 журнал2 п + п (журнал2 нет)2нет2 журнал2 нетМы2 войти п)
n-лог3 n+nlog2 нетn-лог3 н, нлог2 нетO (n журнал n)
  3 бревна8 п+лог2 журнал2 журнал2 нет3 бревна8 нетО (журнал п)
0,100н+0,01н20,01n2Мы2)
0,01н+100н2100н2Мы2)
2н+н0.5 +0,5н1.250,5н1.25Мы1.25)
0.01nlog2 п + п (журнал2 нет)2п (журнал2 нет)2О (п (лог п)2)
100nlog3 п+п3 + 100ннет3Мы3)

Инструкции ниже показывают некоторые особенности нотации «Big-Oh» для функций f ≡ f(n) и g ≡ g(n). Определите, является ли каждое утверждение ИСТИННЫМ или ЛОЖНЫМ, и исправьте формулу в последнем случае.

ФункцияПравда или ложь?После исправления
 О (е + г) = О (е) + О (г)ЛОЖНЫЙO (f + g) = max {O (f), O (g)}
O(fg) = O(f) O(g)ПРАВДА 
 если g = O(f) и h = O(f), то g = O(h)ЛОЖНЫЙесли g = O(f) и f = O(h), то g = O(h)
5n + 8n 2 + 100n 3 = O(n 4 )ПРАВДА 
5n+8n 2 +100n 3 = O(n 2 log n)ЛОЖНЫЙМы3 )

Делиться
ru_RURU
%d такие блоггеры, как: