Сложность алгоритма. Классификация алгоритмов по сложности



Глава 3. РАЗМЕР ЗАДАЧИ. СЛОЖНОСТЬ АЛГОРИТМА

3.1. Размер задачи. Скорость роста

Все решаемые задачи требуют предварительного задания исходных данных. Как правило, в них можно выделить характерное число, определяющее величину этих данных. Например:

а) при проверке, будет ли заданное число простым или составным, характерным является само число,

б) при поиске максимального элемента массива - длина массива.

При вводе в ЭВМ исходные данные кодируются каким–либо способом. Числовые данные обычно представляют в позиционных системах счисления. Символьная информация задаётся в стандартных кодах либо в специальном графическом представлении.

Как правило, с точки зрения принципиального решения задачи все способы кодирования эквивалентны. Однако в ряде случаев за счёт более удобной формы представления можно использовать более простой или быстрый алгоритм.

Размером задачи называют длину последовательности символов, в которой закодированы все исходные данные.

Для ЭВМ размер памяти обычно оценивается числом байтов – последовательностей из восьми бинарных разрядов.

С ростом n размер задачи всегда возрастает, однако в одних случаях необходимое число символов возрастает быстрее, чем в других. Для оценки поведения функций, зависящих от целочисленных натуральных характеристических параметров, вводят понятие скорости роста.

Рассмотрим на множестве натуральных чисел N функции f(ng(n).

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

С1 f(n) ≤ g(n)≤ С2 f(n), где С1>0,С2>0 – некоторые константы.

2. Скорость роста функции g(n) большескорости роста функции f(n), если для любой сколь угодно большой константы С существует некоторое n0, начиная с которого выполняется условие: 

С f(n) ≤ g(n).

3. Скорость роста функции g(n) ограничена снизускоростью роста функции f(n),если при всех достаточно больших n, начиная с некоторого n0, выполняется:

С f(n) ≤ g(n), где С – константа.

4. Скорость роста функции g(n) ограничена сверхускоростью роста функции f(n),если при всех достаточно больших n, начиная с некоторого n0, выполняется условие:

g(n) ≤ С f(n),  где С – константа.

Данное определение позволяет сравнивать между собой скорости роста функций достаточно произвольного вида – как имеющих, так и не имеющих предел отношения g(n)/f(n)при n® ¥ .

Замечание. Если скорость роста функции g(n)равна скорости роста функции f(n), то скорость роста f(n) ограничивает скорость роста g(n)и сверху и снизу.

Пример 1. Рассмотрим задачу с характерным параметром n, у которой входными данными являются все простые делители числа n, не равные единице. С увеличением n число делителей k(n)будет постоянно изменяться в пределах от 1 (у простого числа) до log2n (у степеней2). Поэтому для длины входа k(n)не существует элементарной монотонной функции с одинаковой скоростью роста. Для неё можно только лишь указать ограничения, верные при любых n: 1≤ k(n) ≤ log2n.

В общем случае для каждой положительной функции натурального параметра k(n) возможны следующие варианты:

1) не существует монотонной функции f(n)со скоростью роста, равной k(n), но при всех n, начиная с некоторого n0, возможны лишь оценки:

Cн fн(n) ≤ k(n) ≤ Cв fв(n),

где Cн>0, Cв>0 – нижняя и верхняя константы, fн(n), fв(n)– различные функции.

2) существует монотонная функция f(n), имеющая одинаковую скорость роста с k(n), для которой по определению при всех n, начиная с некоторого n0, выполняется:

Cн f(n) ≤ k(n) ≤ Cв f(n),

где Cн, Cв – константы,

В варианте 2) предел отношения k(n)/f(n) при n® ¥ может:

 а) не существовать и

 б) существовать, при этом:

Случай 2 б) является наиболее распространенным при анализе скорости роста реальных функций натурального параметра. Константу Ср в приведенном выше пределе назовем константой скорости роста, а соответствующую скорость роста – устойчивой.

Функции g(n), зависящие от натурального параметра n, могут иметь любой вид, однако скорости их роста f(n) для большей наглядности и упрощения сравнений выражают через модельные элементарные функции (логарифмы, степенные, показательные и др) либо их произведения. Наиболее часто используют степенные функции nα. Приα = 1 скорость роста функции nα называют линейной, при α =2 – квадратичной, при α =3 – кубическойи т.д. Все скорости роста вида nα называют полиномиальными. С увеличением показателя α полиномиальная скорость роста также возрастает.

Существуют функции, скорости роста которых превосходят при n→ ∞любую (со сколь угодно большим показателем α) полиномиальную скорость. Например,2n, еn, n!. Скорости такого типа называют экспоненциальными.

Из двух функций g1(n), g2(n) с одинаковой устойчивой скоростью роста f(n) меньшие значения в пределе будет иметь функция с меньшей константой скорости роста Ср.

Пример 2. Определить скорость роста f(n)функции g1(n)=(n–5)/3, константу скорости роста Ср, а также определить пороговое значение параметра n0и константы С1 , С2, при которых справедливо соотношение: С1 f(n) ≤ g(n) ≤ С2 f(n).

Решение. Так как при n®¥предел отношения g1(n)/n существует и равен 1/3, то скорость роста функции g1(n) равна линейной полиномиальной f(n)=n1, а константа скорости роста Ср =1/3.

Определим параметры n0, С1, С2. Для этого используем следующие соотношения :

(1/6)× n 1£ (n-5)/3 £ (1/3) × n 1.

Правое неравенство очевидно и выполняется при любых n, константа (1/6) в левой части задана произвольно из условия (1/6) < (1/3), величину n0 определим из левого неравенства:

(1/6)× n1£ (n – 5)/3Þ3× n £6× n –30Þ3× n ³ 30Þ n ³10.

Ответ: f(n)=n1, Ср =1/3, n0=10,  С1 = 1/6, С2 =1/3.

Пример 3. Определить скорость роста f(n)функции g2(n)=0,25×(n–1)(n+2), константу скорости роста Ср, а также определить пороговое значение параметра n0, нижнюю и верхнюю константы С1 , С2 , при которых справедливо соотношение С1 f(n)≤ g(n) ≤ С2f(n).

Решение. При n®¥предел отношения g2(n)/n2 существует и равен 1/4. Следовательно, скорость роста функции g2(n)равна квадратичной полиномиальной f(n)=n2, Ср =1/4.

Определим n0 , С1 , С2 . Для этого используем соотношение

n2/4 £ 0,25×(n–1)(n+2) £ n2/3.

Определим граничное значение n0, начиная с которого будут выполняться неравенства в левой и правой частях.

Левая часть:

n2/4 £0,25× (n–1)(n+2)Þ n2£ n2+n –2Þ n ³2Þ n0 =2.

Правая часть:

0,25×(n–1)(n+2)£ n2/3 Þ3n2+3n–6 £4n2Þ n2–3n+6 ³0.

Так как дискриминант уравнения отрицательный, то данное неравенство справедливо при любых  n.

Ответ: f(n)=n2, Ср =1/4, n0=2,  С1 = 1/4, С2 =1/3.

Обозначим скорость роста размера задачи через r(n). Рассмотрим примеры её определения.  

Пример 4. При проверке, будет ли число n простым или составным, r(n) задачи определяется длиной записи самого числа n. В позиционной системе с основанием р  число бит, в записи числа n равно ]logр n[, а размер задачи в байтах r(n)=]logр n[/8.

Пример 5.Задача коммивояжера (ЗК). Задано n упорядоченных населенных пунктов {vn}={v1, v2, ... , vn}. Все расстояния между ними известны и заданы симметричной матрицей стоимости С размером n ´ n, элементы которой удовлетворяют неравенству треугольника, т.е. при любых i, j, k, лежащих в пределах 1≤ i, j, k n, справедливы соотношения: с i j = с j i ;   с i j + с j kс i k .

Коммивояжеру требуется выбрать из всего множества циклических обходов {О (vn )} пунктов {vn}, такой обход Оnопт, у которого общая длина

                n-1

 L(Оnопт)= ∑ с i j, i (j+1)  + с i n, i 1

                  j=1

будет минимально возможной.

В задаче изо всех исходных данных наиболее быстро (n2) растёт число элементов симметричной матрицы стоимости С размером n´n. Поэтому скорость роста размера данной задачи будет квадратичной полиномиальной –  r(n)= n2.

Вопросы для проверки знаний.

1. Что называют размером задачи и в каких единицах ее измеряют в ЭВМ ?

2. Что означает, что функции g(n) и f(n)имеют одинаковую скорость роста ?

3. Что означает, что скорость роста одной функции большескорости роста другой функции ?

4. Что означает, что скорость роста функции g(n) ограничена снизускоростью роста функции f(n) ?

5. Могут ли значения функции g(n), у которой скорость роста ограничена сверхускоростью роста функции f(n), превышать значения данной функции ?

6. В каком случае скорость роста функции называют устойчивой и что называют константой скорости роста  ?

7. Какие скорости роста функций называют полиномиальными, линейными, квадратными и кубическими ?

8. Какие скорости роста функций называют экспоненциальными ?

Практические задания.

1. Определить постоянную скорость роста f(n)функции g(n) =5×(n-1)×(n+3)/(n+5), константу скорости роста Ср , а также найти значения n0 , С1 , С2 , при которых справедливо соотношение С1 f(n) ≤ g(n) ≤ С2f(n).

2. Найти скорость роста f(n)и константы скорости роста Ср функций:

а) g1(n)=0,1× (n! –2n2+3n+10)/(3n–1);

б) g2(n)=(еn+3n10+ 7)(4n3 -6n2 + 2n + 5);

в) g3(n)=2n+ n n n2 .

3. Доказать, что:

а) скорость роста функции n! превосходит в пределе при n→∞скорость роста функции 2n ;

б) скорость роста функции 2n  превосходит в пределе при n→ ∞любую (со сколь угодно большим показателем α) скорость роста полиномиальной функции nα .

4. Выяснить для функции скорости роста f(n) = n2(1+(–1)n) +2n+1:

а) устойчивость скорости роста,

б) ограниченность снизу,

в) ограниченность сверху.

Сложность алгоритма. Классификация алгоритмов по сложности

Размер задачи r(n) оценивает величину памяти, необходимой для представления исходных данных задачи в ЭВМ.

Однако, возможность представления условия задачи в памяти ЭВМ не гарантирует её практического решения. Во-первых, как правило, нужна дополнительная память для хранения промежуточных и окончательных результатов счёта.

Во–вторых, время решения может оказаться недопустимо большим. И первое условие и второе зависят от алгоритмов, применяемых при решении задачи.

Размер дополнительной памяти, как правило, определить несложно. Рассмотрим время счёта. В процессе реализации расчётного алгоритма, выбранного для решения задачи, необходимо выполнять определённое число элементарных арифметических, логических и других операций – сложения, вычитания, умножения, деления, возведения в степень, сравнения и т. д.

Пусть в процессе решения задачи при помощи некоторого алгоритма выполняются элементарные операции с номерами 1, 2, ..., k. Среднее время выполнения этих операций на используемой ЭВМ обозначим через t1, ... , tk , число операций, зависящее от применяемого алгоритма решения – через g1(n), ... , gk(n).

Обозначим полное время счёта алгоритма через Т(n).Достаточно точно его можно выразить в виде суммы: Т(n) = Т1(n) + Т2(n)+...+Тk(n),где Т1(n), Т2(n), ...k(n) – общее время выполнения каждой из операций 1,2,...,k. Выражая все величины Тi(n) через ti и gi(n), получим:

Рассмотрим зависимость скорости роста общего времени счета алгоритма Т(n) от чисел выполняемых операций g1(n) – gk(n).

Теорема 3.1 о скорости роста времени счета алгоритма. Пусть при выполнении алгоритма используются элементарные операции 1, 2, ... , k. У операции с номером s (1 £ s £ k) число выполняемых операций gs(n) имеет устойчивую скорость роста fs(n). У остальных операций i (1 £ i  £ k , i ¹ s)числа выполняемых действий gi(n)ограничены сверху функциями со скоростями роста, меньшими fs(n).

Тогда при n→∞ скорость роста общего времени счёта алгоритма Т(n) будет устойчивой и равна скорости роста fs(n) независимо от среднего времени выполнения t1 , ... , tk элементарных операций f1(n), ... , fk(n).

Доказательство. Представим общее время счета алгоритма Т(n) в следующем виде:

У операции s для числа выполняемых действий gs(n)по определению одинаковой скорости роста с fs(n) существуют такие значения n0sÎ`N, С1s>0, С2s >0 , что при " n ³  n0s  выполняется условие: С1s fs (n) ≤ gs (n) ≤ С2s fs (n).

Рассмотрим остальные операции i (1 £ i  £ k , i ¹ s). Очевидно, gi (n) ³0. По определению ограниченности сверхудля любой операции i существуют такие значения n0iÎ N, С2i >0 , что при " n ³ n0i  выполняется условие: gi (n) ≤ С2i fi (n).

Принимая:

зависимость всех пар функций gi(n), fi(n)при " n ³ n0 можно представить в унифицированном виде: gi (n) ≤ С2fi (n), а для общего времени счета – записать неравенство:

      

Поскольку все скорости роста fi (n)при i ¹ s меньше скорости роста fs (n), то по определению для константы С=1 всегда найдется такое значение параметра 0i Î`N, что при "n³  n¢0i  справедливо: fi(n) ≤ fs(n). Принимая в качестве 0= max(n0,01, … , ik), получим, что при " n ³0 правое неравенство может быть представлено в виде:

 

 Вводя новые константы:

 

получим, что при " n ³0 выполняется соотношение, доказывающее справедливость теоремы:

С1× fs (n) ≤ T(n) ≤ С2× fs (n),

т.е. одинаковую скорость роста у общего времени счета T(n)и у максимальной из скоростей роста числа элементарных операций алгоритма, что и требовалось доказать.

При анализе элементарных арифметических операций алгоритма и подсчете их числа необходимо учитывать тип величин, с которыми выполняются данные действия. Представление целых и вещественных чисел в памяти ЭВМ различно. Операции с целыми числами в процессоре выполняет арифметико-логическое устройство, а операции с вещественными числами - сопроцессор для чисел с плавающей запятой.

Замечания. 1. Одинаковая скорость роста числа выполняемых операций может быть у нескольких элементарных операций. Справедливость доказанного утверждения при этом сохраняется.

2. Если у максимально растущих чисел операций gi(n)скорость роста не является устойчивой, а известна лишь верхняя ее оценка, то справедлив следующий вариант теоремы 3.1.

Теорема 3.2 о верхней оценке скорости роста времени счета алгоритма. Пусть при выполнении алгоритма используются элементарные операции 1, ... , k. Числа этих операций g1(n), … , gk(n)ограничены сверху скоростью роста функции f(n).

Тогда при n→∞ скорость роста общего времени счёта алгоритма Т(n) также будет ограничена сверху скоростью роста функции f(n).

Доказательство Теоремы 3.2 можно выполнить по аналогии с доказательством Теоремы 3.1.

Следствие. Скорость роста общего времени счёта алгоритма Т(n) определяется скоростями роста f1(n), ... , fk(n) чисел элементарных операций g1(n), ... , gk(n) либо их верхними границами.

Скорость роста общего времени счёта алгоритма Т(n) называют сложностью алгоритма и обозначают через f(n).

В зависимости от сложности все комбинаторные алгоритмы делятся на несколько основных групп.

Полиномиальными называются алгоритмы, сложность которых ограничена полиномом.

Примеры 1: а) f(n) = n, б) f(n) = n 2, в) f(n) = n×logn < n 2.

Экспоненциальными называются комбинаторные алгоритмы, сложность которых в пределе при бесконечном возрастании n превышает полином любой степени.

Примеры 2: а) f(n) = е n, б) f(n) = n n, в) f(n) = n!, г) f(n) =2 n.

Субэкспоненциальными называются алгоритмы, сложность которых в пределе при бесконечном возрастании n превышает полином любой степени, но меньше 2 nδ при любом δ>0.

Пример 3. f(n) = n logn.

Рассмотрим примеры расчета сложности алгоритмов.

Пример 4. Задача: упорядочить по убыванию элементов линейный числовой массив А[n]i.

Предлагаемый алгоритм решения: внутренняя (без использования дополнительной памяти) сортировка с выбором. В данном алгоритме выполняется n –1 шаг. На первом определяется минимальный из n элементов a1, a2, … , an и путем обмена с a1 помещается на первое место. На втором определяется минимальный из n–1 элементов a2, … , an и путем обмена с a2 помещается на второе место и т.д.

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

Решение. В алгоритме используются две основные операции – 1) сравнение величин элементов массива и 2) обмены пар элементов местами. Определим в зависимости от параметра задачи n числа выполняемых основных операций. Обозначим их, соответственно, g1(n) и g2(n). Так как всего выполняется n –1 шаг, на каждом один обмен, то g2(n) = n – 1. На первом шаге выполняется (n - 1) сравнение, на втором – (n –2), … , на последнем (n – 1) –том – одно сравнение. g1(n) определяем как сумму арифметической прогрессии:

g1(n) = (n – 1)+ (n –2)+…+1 = n(n -1)/2.

Так как для найденных функций выполняются следующие предельные оценки:

то по определению g1(n) имеет квадратичную полиномиальную скорость роста, а g2(n) – линейную.

Ответ: поскольку у операции сравнения 1 устойчивая квадратичная полиномиальная скорость роста, а у операции обмена 2 – устойчивая линейная скорость, то по Теореме 3.1 скорость роста общего времени счёта (сложность) алгоритма будет устойчивой и равна максимальной из скоростей роста чисел элементарных операций, т.е. будет квадратичной полиномиальной.

Пример. 5. Необходимо определить сложность алгоритма, заключающегося в  полном переборе обходов в задаче коммивояжера (ЗК) для n населенных пунктов {vn }={v1, v2, ... , vn}(пример 5 п.3.1).

Решение. На каждом из (n–1)!/2возможных обходов при полном переборе требуется выполнить следующие операции:

1) сформировать сам обход Оn={vi1, vi2, ... , vin} ,

2) вычислить длину обхода {vi1, vi2, ... , vin} L(Оn):

3) сравнить длину обхода L(Оn) с текущим значением минимума Lmin и при необходимости – скорректировать Lmin.

Поскольку формирование обхода Оn требует n элементарных операций, вычисление длины – также n сложений, то числа выполняемых операций g1(n) (формирование обхода), g2(n) (сложение), g3(n) (сравнение длин обхода) будут следующими:

g1(n)= n! /2, g2(n)= n! /2, g3(n)= (n–1)!/2 .

Для найденных функций выполняются следующие предельные оценки:

По Теореме 3.1 сложность алгоритма будет устойчивой и равна максимальной из скоростей роста чисел элементарных операций, т.е. будет факториальной по n.

Ответ: Сложность алгоритма относится к экспоненциальному типу.

Сравнительные значения величин функций для трёх рассмотренных типов скоростей роста при значениях характерного параметра n = 10, 100, 1000 приведены в таблице.

NN Вид алгоритма   Функция n = 10  n =100 n = 1000

                                           n 1              10      102        103

                                                                  logn   10     2×102   3×103                                                                              

1. Полиномиальный    n 2               102    104        106 

                                          n 3              103    106         109

                                          n10             1010  1020        1030

2. Субэкспоненциальный nlnn    200,7 1,62×1013 5,29×1029                                      

                                          еn    0.22×105 0.27×1043 0.78×10208

3. Экспоненциальный    2n      0.1×104 0.12×1031 0.1×10301

                                           n!  0.36 ×107     10158     4×102567

                                          nn                1010 10200     103000


Дата добавления: 2018-04-15; просмотров: 1120; Мы поможем в написании вашей работы!






Мы поможем в написании ваших работ!