Оценка на изчислителната сложност. Времева сложност на алгоритъма

Определяне на сложността на алгоритъм

Оценката на функцията на сложността, получена при асимптотичния анализ, се нарича сложност на алгоритъма.

Трябва да се има предвид, че има няколко оценки за сложността на алгоритъма.

Асимптотичното поведение на функцията на сложността е оперативната сложност. В допълнение към него можете да посочите следните видове трудности.

Временносложност - асимптотична оценка на времето за работа на алгоритъма върху входните данни за дължина П.Очевидно е, че при липса на паралелизиране на изчислителните процедури, времето за изпълнение на алгоритъма се определя еднозначно от броя на извършените операции. Постоянните коефициенти, изразяващи продължителността на операциите, не влияят на реда на времева сложност, така че формулите за оперативна и времева сложност често съвпадат една с друга.

капацитивенсложност - асимптотична оценка на броя на едновременно съществуващи скалари при изпълнение на алгоритъма върху входни данни с дължина П.

Структурнисложност - характеристика на броя на управляващите структури в алгоритъма и спецификата на тяхното взаимно положение.

когнитивнисложност - характеристика на наличието на алгоритъм за разбиране от експерти в областите на приложение.

Видове и обозначение на асимптотика

При асимптотичния анализ на алгоритмите е обичайно да се използва нотацията на математическия асимптотичен анализ. В този случай се разглеждат три оценки (асимптотика) на сложността на алгоритмите, които се обозначават по следния начин:

1) /(i) = O^(n))- асимптотично точна оценка на функцията на сложност /(«), или оперативната сложност на алгоритъма;
2) /(n) = 0(§(n)) -асимптотично точна горна оценка на функцията на сложност /( П);
3) /(l) = ?2(#(l)) - асимптотично точна долна оценка на функцията за вложен труд /( P).

Вместо обозначение C1^(n))много често по-простото o(^(“)) се използва с буквата “o” с малка буква.

Нека обясним семантиката на формулите с помощта на пример: ако е написано / (n) = 0 (^2 (n)), ТОГАВА ТОВА означава, че функцията g(n)=og2 (н)е асимптотично точна оценка на функцията на сложност /(«). Всъщност има определение от две позиции под формата на твърдение:

Ако f(n)= @(log2(")),

mo g(n)\u003d дневник 2 (l) - асимптотично точна оценка на f(n).

Имайте предвид, че константният фактор не влияе на реда на сложност на алгоритъма, така че основата на логаритъма се пропуска при определяне на логаритмичната сложност и те просто пишат f(l) = @(lо§(l)), което означава, че логаритъмът има произволна основа, по-голяма от единица.

Формални дефиниции на асимптотика

Асимптотично точна оценка на функцията за вложен трудот, от 2 , l 0 , така че за l>l 0 функцията /(l), до постоянни множители, не се различава от функцията g( k), след това функцията g(n)се нарича асимптотично точна оценка на функцията /(k).

3 s ] , s 2 e F, с х > 0, с 2 > 0:
- (3 l 0 e K, l 0 > 0: (/l e K, l > l 0:0 g(n) /(l) = 0(?(l)),

където 9^, N са множествата от всички реални и естествени числа, съответно.

Асимптотично точна горна граница за функцията на сложностустно дефинирани по следния начин: ако има положителни числа оти l 0 , така че за l>l 0 функцията /(l) расте не по-бързо от функцията g(n)до постоянен коефициент c, след това функцията g(n)се нарича асимптотично точна горна граница за функцията Ап).

По-точно формално определение има формата:

3 отд %s > 0:
- (3 l 0 e X, l 0 > 0: (/l e K, l > l 0:0 s? #(l))) 0(g(n))

Асимптотично точна долна граница за функцията на сложностустно дефинирани по следния начин: ако има положителни числа оти l 0 , така че за l>l 0 функцията /(l) расте не по-бавно от функцията g(n)до постоянен коефициент от,тогава функцията?(k) се нарича асимптотично точна долна граница за функцията

По-точно формално определение има формата:

3 отд 9^, от > 0:
- (3 i 0 e X, i 0 > 0: (/i e K, т.е > аз 0: 0 с? g(n)

/(аз) = 0.^(n))

Обърнете внимание на следното:

1) неравенствата, посочени във формалните дефиниции на асимптотиката, в общия случай могат да бъдат задоволени не от една, а от определен набор от функции, често с неизброим набор от термини, така че конструкциите Q(g(n)), 0^(n))И 0.^(n))символизират набор от функции, с което се съпоставя изследваната функция на вложения труд /(i); поради това в обозначението на асимптотиката на формата /(n) = 0(?(n)), /(/0 = 0(? max (n)), Dn) = ?2(? m1n (n )) вместо знака "= » би било по-рационално да се използва знакът "e";
2) дизайни (d^(n)), 0^(n))И ?1^(n)),използвани като символи за определени количества, трябва да се чете съответно, както следва: всяка функция, която е една и съща, не расте по-бързо и не расте по-бавно g(n).

Съвпадение и разлика на асимптотиката

Нека обърнем внимание на следния факт: оценката f(s) = 0(?(s)) установява за f(s) както горната, така и долната оценка, тъй като нейното определение предполага валидността на връзката c g g(n)

Следното свойство на асимптотиката е съвсем очевидно: ако оценката φ(n) = ©^(n))съществува, то равенствата /( П) = 0(^(n)) и /(n) = ?2(#(n)), т.е. горната и долната оценка на интензивността на труда съвпадат една с друга; ако /(i) = 0(? max (i)) и φ(n) = C1^ mn (n)), И g max (n)Фg m 1n(i), тогава няма функция g(n),такъв, че /(i) = 0(?(i)).

Съвпадението на горната и долната оценка на интензивността на труда е възможно в следните случаи:

1) функцията на сложност за всички стойности на входната дължина е детерминирана (неслучайна) функция, т.е. броят на извършените операции не зависи от спецификата на стойностите на първоначалните данни; такива са например функциите на зависимост на броя на операциите за умножение и деление от броя на неизвестните величини в алгоритъма за решаване на системи от линейни алгебрични уравнения по метода на IS разширяване;
2) функцията на интензивността на труда е случайна функция, т.е. броят на извършените операции зависи от спецификата на първоначалните данни и (или) реда на тяхното пристигане и можете да посочите функциите / m | обаче и двете от тези функции имат едни и същи доминанти, например те са полиноми на същия ред.

Има три важни правила, които трябва да имате предвид, когато става въпрос за оценка на реда на оперативна сложност:

1) постоянните фактори нямат значение за определяне на реда на сложност, т.е. 0 (k? g(n)) = 0(g(")) ;
2) редът на сложност на произведението на две функции е равен на произведението на тяхната сложност, тъй като равенството е вярно:
0(gl(i) §2(i)) = 0 (?| (i)) 0 (#2(i));
3) редът на сложност на сбора от функции е равен на реда на доминанта на членовете, например: 0(i e + n 2 + n) = 0 (i 5).

Горните правила използват символа само на една асимптотика 0("), но те са валидни за всички асимптотични оценки - и за 0( ) , И &.{ ).

В набора от елементарни функции можете да посочите списък с функционално доминиране: ако е променлива, a,b-числови константи, тогава следните твърдения са верни: i" доминира i!; i! доминира а"; а"доминира Zj", ако a>b a pдоминира Пб, ако но> 1 за всеки бд 9? ; n aдоминира а/ ако а>б i доминира log q(i), ако но > 1.

Оценка на средната интензивност на труда

На практика ре Изчисленията от значителен интерес представляват оценката /(n) на математическото очакване на сложността на M, тъй като в по-голямата част от случаите /(n) е случайна функция. Въпреки това, в процеса на експериментални изследвания на алгоритми със случаен /(n), възниква допълнителен проблем - изборът на броя на опитите за надеждна оценка на M. Преодоляването на този проблем е централна задача в . Предложеното решение се основава на използването на бета разпределението за приблизително /(n). Това е много конструктивна и универсална техника. Въпреки това, в съвременни условия, когато производителността на компютъра е доста висока, в много случаи е възможно да се използва по-опростен метод за избор на обхвата на тестовете, базиран на наблюдение на текущата променливост на стойностите f(n) -стойностите се оценяват, докато дисперсията на оценките стане по-малка от посочената грешка.

Оценяване на оперативната сложност на алгоритъм

Сложността на алгоритъма може да се определи въз основа на анализа на неговите управляващи структури. Алгоритмите без цикли и рекурсивни извиквания имат постоянна сложност. Следователно дефинирането на сложността на алгоритъм се свежда главно до анализа на цикли и рекурсивни извиквания.

Помислете за алгоритъма за изтриване да се-ти елемент от масив с размери П, състояща се от преместване на елементите на масива от (до + 1) -то до П-върнете една позиция назад в началото на масива и намалете броя на елементите Пза единица. Сложността на цикъла за обработка на масива е О (п-к),тъй като тялото на цикъла (операция преместване) се изпълнява настолен компютърпъти, а сложността на тялото на цикъла е 0(1), т.е. е константа.

В разглеждания пример сложността се характеризира с асимптотика 0("), тъй като броят на операциите, извършени в този алгоритъм, не зависи от спецификата на стойностите на данните. Функцията на сложността е детерминистична и всички видове асимптотика съвпадат помежду си: f(n) = Q(n-k), f(n) = 0(n-k)И f(n) = Q(n- до). Този факт се доказва от посочването точно на ©( ). Използвайте 0(*) и/или?2(*) само ако тези асимптотики се различават.

Типът цикъл (for, while, repeat) не влияе на сложността. Ако един цикъл е вложен в друг и двата цикъла зависят от размера на една и съща променлива, тогава цялата конструкция се характеризира с квадратична сложност. Влагането на повторения е основен фактор за нарастването на сложността. Като пример представяме сложността на добре познатите алгоритми за търсене и сортиране за масив с размери П:

брой операции за сравнение при последователно търсене: 0(n);
брой на операциите за сравнение при двоично търсене: 0 (log 2 П);
брой операции за сравнение при прост обменен метод (сортиране с балон): 0(n 2);
брой операции на пермутация при сортиране с балончета: 0(n 2);

Обърнете внимание, че броят на операциите за сравнение в метода за прост обмен има асимптотика 0(n 2), а броят на операциите за пермутация има две различни асимптотики 0 (стр 2)и?2(0), тъй като броят на сравненията не зависи от спецификата на стойностите на сортираните данни, докато броят на пермутациите се определя от тази специфика. Пермутациите може изобщо да не се извършват - ако масивът от данни е правилно подреден първоначално или броят на пермутациите може да е максимален - от реда П 2 , - ако сортираният масив първоначално е подреден в обратна посока.

Име на функцията g(n)в асимптотиката /(x) = @(x(x)) и /(a) = 0(g(n))функцията на сложност /(«) се използва за характеризиране на алгоритъма. Така се говори за алгоритми с полиномна, експоненциална, логаритмична и т.н. сложност.

Със сигурност често сте срещали обозначения като O (log n) или сте чували фрази като "логаритмична изчислителна сложност" във връзка с всякакви алгоритми. И ако все още не разбирате какво означава това, тази статия е за вас.

Оценка за трудност

Сложността на алгоритмите обикновено се оценява от времето за изпълнение или от използваната памет. И в двата случая сложността зависи от размера на входните данни: масив от 100 елемента ще се обработва по-бързо от подобен от 1000. В същото време малко хора се интересуват от точното време: зависи от процесора, тип данни, език за програмиране и много други параметри. Важна е само асимптотичната сложност, т.е. сложността, тъй като размерът на входа клони към безкрайност.

Да кажем, че някой алгоритъм трябва да изпълни 4n 3 + 7n условни операции, за да обработи n входни елемента от данни. С увеличаване на n общото време на работа ще бъде значително по-засегнато от повишаване на n до куба, отколкото умножаването му по 4 или добавянето на 7n. Тогава казваме, че времевата сложност на този алгоритъм е равна на O(n 3), т.е. зависи кубично от размера на входните данни.

Използването на главно O (или така наречената O-нотация) идва от математиката, където се използва за сравняване на асимптотичното поведение на функциите. Формално O(f(n)) означава, че времето за изпълнение на алгоритъма (или количеството заета памет) нараства в зависимост от количеството входни данни не по-бързо от някаква константа, умножена по f(n) .

Примери

O(n) - линейна сложност

Такава сложност има например алгоритъмът за намиране на най-големия елемент в несортиран масив. Трябва да преминем през всички n елемента от масива, за да разберем кой е най-големият.

O(log n) - лог сложност

Най-простият пример е двоичното търсене. Ако масивът е сортиран, можем да проверим дали съдържа конкретна стойност чрез разполовяване. Нека проверим средния елемент, ако е по-голям от желания, тогава ще изхвърлим втората половина на масива - определено го няма. Ако по-малко, тогава обратното - изхвърляме първоначалната половина. И така ще продължим да разделяме наполовина, в резултат на което ще проверим log n елементи.

O(n 2) - квадратична сложност

Такава сложност има например алгоритъмът за сортиране при вмъкване. В каноничната реализация той се състои от два вложени цикъла: единият за преминаване през целия масив, а вторият за намиране на място за следващия елемент във вече сортираната част. По този начин броят на операциите ще зависи от размера на масива като n * n , т.е. n 2 .

Има и други оценки на трудност, но всички те се основават на същия принцип.

Също така се случва времето за работа на алгоритъма изобщо да не зависи от размера на входните данни. Тогава сложността се обозначава като O(1) . Например, за да определите стойността на третия елемент от масива, не е необходимо да помните елементите или да ги преглеждате няколко пъти. Винаги трябва просто да изчакате третия елемент във входния поток от данни и това ще бъде резултатът, чието изчисляване за произволно количество данни отнема същото време.

По същия начин оценката се извършва от паметта, когато е важна. Алгоритмите обаче могат да използват значително повече памет, когато увеличават размера на входните данни, отколкото други, но въпреки това работят по-бързо. И обратно. Това помага да се изберат най-добрите начини за решаване на проблеми въз основа на текущите условия и изисквания.

срок: 8 януари 2010 г

Преди крайния срок статията не трябва да бъде редактирана от други участници в проекта уебсайт. В края му всеки участник има право да коригира тази статия по свое усмотрение и да изтрие това предупреждение, показано с помощта на шаблона ((Задача)).

Вижте също насокиотносно използването на ресурса уебсайтв образователния процес.

Теория на изчислителната сложностКлон на изчислителната теория, който изучава количеството работа, необходима за решаване на изчислителен проблем.

Една задача се счита за трудна, ако решението на проблема изисква голямо количество ресурси, независимо от алгоритъма, използван за решаването й. Теорията формализира това интуитивно понятие, като въвежда математически модели на изчисление за изследване на тези проблеми и количествено определяне на количеството ресурси, необходими за решаването им, като например използване на време и памет. Възможни са и други мерки за сложност, като например: броя на съобщенията (комуникационна сложност), броя на елементите във веригата от функционални елементи (сложност на веригата) и броя на процесорите. По-специално, теорията за изчислителната сложност дефинира практически граници за това какво могат и какво не могат да правят компютрите.

Тясно свързан с теорията на изчислителната сложност е анализът на алгоритмите и теорията на изчислимостта. Основната разлика между теорията на изчислителната сложност и анализа на алгоритмите е, че последният се занимава с анализа на количеството ресурси, необходими на даден алгоритъм за решаване на проблем, докато първият задава по-общ въпрос за всички възможни алгоритми, които могат да бъдат използвани за реши същия проблем проблем. По-точно, теорията за изчислителната сложност се опитва да класифицира проблеми, които могат или не могат да бъдат решени с подходящо количество ограничени ресурси. От своя страна, налагането на ограничения върху наличните ресурси е това, което отличава теорията на изчислителната сложност от теорията на изчислимостта: последната пита какви проблеми по принцип могат да бъдат решени алгоритмично, без да се ограничават изчислителните ресурси.

Изчислителни проблеми

Екземпляри на задачи

Изчислителните проблеми (задачи) могат да се разглеждат като безкраен набор от двойки: (проблемна инстанция, решение за даден екземпляр). Входният низ за изчислителен проблем е низ, описващ екземпляра на проблема. Изходният низ за изчислителен проблем е описание на решението за проблемния екземпляр, описан от входния низ. Например, проблемът за разпознаване на простотата на число: екземпляр на проблема е число, за което трябва да се определи дали е просто или не, решението е низът "да", ако това число е просто и "не" " в противен случай. Теорията на изчислителната сложност разглежда само масивни проблеми, т.е. изискването наборът от екземпляри на задачите да е безкраен е задължително.

Изглед на задачите

Когато се разглеждат изчислителни проблеми, описанието на проблемен екземпляр е низ над азбуката. По правило азбуката се приема като двоична (т.е. множеството (0,1)). Различни математически обекти трябва да бъдат кодирани съответно. Така, например, цели числа могат да бъдат представени в двоичен вид, а графиките могат да бъдат кодирани директно чрез техните матрици на съседство или чрез тяхното кодиране на списъци на съседство в двоичен вид.

Задачи за разпознаване

Проблемът с разпознаването е един от централните обекти на изследване в теорията на изчислителната сложност. Задачата за разпознаване е специален тип изчислителна задача, отговорът на която е „да“ или „не“ (1 или 0). Проблемът за разпознаване може да бъде формулиран като проблем дали даден входен низ принадлежи на определено подмножество (език) от множеството от всички входни низове. Входящият низ на задачата принадлежи на съответния език, ако и само ако отговорът на този низ е "да". По този начин задачата за разпознаване е задачата да се разпознае, че един входен низ принадлежи на определен език.

Пример за проблем с разпознаването. Входен низ: описание на произволна графика. Проблемът е да се реши дали дадената графика е свързана или не. Езикът на свързаните графи е наборът от описания на всички свързани графи. За да се получи точна дефиниция на този език, трябва да се реши как графиките се кодират като двоични низове.

Задачи за търсене

Задачата за търсене е изчислителна задача, при която изходната стойност е по-сложна, отколкото в задачата за разпознаване (тоест, не е само „да“ или „не“).

Пример за проблем с търсенето е проблемът с пътуващия търговец. Проблемът с пътуващия търговец е един от най-известните задачи за комбинаторна оптимизация. Задачата е да намерите най-изгодния маршрут, минаващ през посочените градове поне веднъж и след това да се върнете в първоначалния град. В условията на задачата се посочват критерият за рентабилност на маршрута (най-кратък, най-евтин, кумулативен критерий и др.) и съответните матрици на разстояния, разходи и т. н. По правило се посочва, че маршрутът трябва да преминава през всеки град само веднъж - в такъв случай изборът се прави между циклите на Хамилтон. Входен низ: описание на претеглена (т.е. с цифрови знаци по ръбовете) графика. Изходният низ е описание на оптималния маршрут на продавача.

Съществува двойна връзка между задачите за разпознаване и задачите за търсене. Проблемът с търсенето може да бъде формулиран като проблем за разпознаване. Например, за задачата за търсене "умножаване на две числа", съответната задача за разпознаване на двойки може да бъде представена като набор от тройки (A, B, C), така че отношението A × B = C е удовлетворено.

Измерване на трудност

Теорията на изчислителната сложност възникна от необходимостта да се сравни скоростта на алгоритмите, ясно да се опише тяхното поведение (време за изпълнение, количество необходима памет и т.н.) в зависимост от размера на входа и изхода.

Броят на елементарните операции, изразходвани от алгоритъма за решаване на конкретен случай на проблема, зависи не само от размера на входните данни, но и от самите данни. Например, броят на операциите на алгоритъма за сортиране с вмъкване е много по-малък, ако входните данни вече са сортирани. За да избегнете подобни трудности, помислете за концепцията за времева сложност на алгоритъма в най-лошия случай.

Времевата сложност на алгоритъма (в най-лошия случай) е функция от размера на входните и изходните данни, равна на максималния брой елементарни операции, извършени от алгоритъма за решаване на проблемен екземпляр с посочения размер. При проблеми, при които размерът на изхода не надвишава или е пропорционален на размера на входа, може да се разглежда времевата сложност като функция само на размера на входните данни.

Подобно на концепцията за времева сложност в най-лошия случай, концепцията за времева сложност на алгоритъм в най-добрия случай се дефинира. Помислете също за концепцията за средното време на алгоритъма, тоест математическото очакване на времето на алгоритъма. Понякога се казва просто: „Временова сложност на алгоритъма“ или „Време на алгоритъма“, отнасяйки се до времевата сложност на алгоритъма в най-лошия, най-добрия или средния случай (в зависимост от контекста).

По аналогия с времевата сложност те определят пространствената сложност на алгоритъма, само че тук се говори не за броя на елементарните операции, а за количеството използвана памет.

Въпреки факта, че функцията за времева сложност на алгоритъма може да се определи точно в някои случаи, в повечето случаи е безсмислено да се търси точната му стойност. Въпросът е, че, първо, точната стойност на времевата сложност зависи от дефиницията на елементарните операции (например, сложността може да бъде измерена в броя на аритметичните операции или операции на машина на Тюринг), и второ, като размерът на входните данни се увеличават, приносът на постоянните коефициенти и членове от по-ниски порядки, фигуриращи в израза за точното време на работа, става изключително незначителен.

Отчитането на големи входни данни и оценката на реда на нарастване на времето за работа на алгоритъма води до концепцията за асимптотична сложност на алгоритъма. В същото време алгоритъм с по-малка асимптотична сложност е по-ефективен за всички входни данни, с изключение, вероятно, за данни с малък размер.

Сложността се определя въз основа на изчислителния модел, в който се извършват изчисленията.

Изчислителни модели

Има много различни модели на изчисление: Post машина, Мински машина, ламбда изчисление, частично рекурсивни функции, нормални алгоритми на Марков, машини с произволен достъп до памет (RAM машини) и т.н. Нека споменем само най-популярния изчислителен модел - Тюринг машина.

Машина на Тюринг

Машината на Тюринг (МТ) е абстрактен изпълнител (абстрактен компютър). Той е предложен от Алън Тюринг през 1936 г. за формализиране на концепцията за алгоритъм.

Машината на Тюринг е разширение на крайния автомат и, според тезата на Чърч-Тюринг, е в състояние да имитира всички други изпълнители (чрез задаване на правила за преход), които по някакъв начин реализират процеса на изчисление стъпка по стъпка, при което всяко изчисление стъпка е съвсем елементарна.

Съставът на машината на Тюринг включва лента, която е безкрайна и в двете посоки (възможни са машини на Тюринг, които имат няколко безкрайни ленти), разделена на клетки и управляващо устройство, което може да бъде в едно от многото състояния. Броят на възможните състояния на управляващото устройство е краен и точно даден.

Контролното устройство може да се движи наляво и надясно по лентата, да чете и записва знаци от някаква крайна азбука в клетките на лентата. Разпределя се специален празен символ, който запълва всички клетки на лентата, с изключение на тези от тях (крайно число), върху които са записани входните данни.

Устройството за управление работи в съответствие с правилата за преход, които представляват алгоритъма, реализиран от тази машина на Тюринг. Всяко правило за преход инструктира машината, в зависимост от текущото състояние и символа, наблюдаван в текущата клетка, да напише нов символ в тази клетка, да премине в новото състояние и да премести една клетка наляво или надясно. Някои състояния на машината на Тюринг могат да бъдат маркирани като терминални, а преходът към всяко от тях означава край на работата, спиране на алгоритъма.

За машината на Тюринг се казва, че е детерминирана, ако всяка комбинация от символ на състояние и лента в таблицата съответства на най-много едно правило. Ако има двойка (символ на лента - състояние), за която има 2 или повече инструкции, такава машина на Тюринг се нарича недетерминистична.

Моделът на машината на Тюринг позволява различни разширения. Може да се разглеждат машини на Тюринг с произволен брой ленти и многоизмерни ленти с различни ограничения; машини, които използват източник на произволност.

Машината на Тюринг е един от основните модели на изчисление в теорията на сложността.

Класове по трудност

Класовете по сложност са набори от изчислителни проблеми, които са приблизително еднакви по отношение на изчислителната сложност. Има класове по езикова сложност и класове по функционална сложност. Класът на сложност на езиците е набор от предикати (функции, които приемат дума като вход и връщат отговор от 0 или 1), които използват приблизително същото количество ресурси за изчисляване. Концепцията за клас на функционална сложност е подобна, с изключение на това, че не е набор от предикати, а набор от функции. В теорията на сложността по подразбиране класът на сложност е класът на сложност на езиците. Типичната дефиниция на клас на сложност изглежда така:

Класът на сложност X е набор от предикати P(x), които са изчислими на машини на Тюринг и използват ресурс O(f(n)) за изчисляване, където n е дължината на думата x.

Ресурсите обикновено се приемат като време за изчисление (броя на работните цикли на машината на Тюринг) или работната площ (броя клетки, използвани на лентата по време на работа). За езици, разпознати от предикати от определен клас (тоест набор от думи, за които предикатът връща 1), също се казва, че принадлежат към същия клас.

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

Класовете обикновено се означават с главни букви. Допълнението към клас C (тоест класът от езици, чиито допълнения принадлежат на C) се обозначава като co-C.

За всеки клас има категория задачи, които са „най-трудни”. Това означава, че всяка задача от клас се свежда до такава задача и освен това самата задача се намира в класа. Такива задачи се наричат пълни задачи за даден клас.

Клас П

Клас P (от английски polynomial) - набор от задачи за разпознаване, които могат да бъдат решени на детерминирана машина на Тюринг за полиномиално време на дължината на входа. По същия начин, за задачи за търсене се дефинира класът FP (от английски функционален полином).

По-формално, разгледайте детерминираните машини на Тюринг, които изчисляват отговора, дадена дума на входната лента от входната азбука. Времето на работа на машина на Тюринг за фиксирана входна дума хе броят на работните цикли на машината на Тюринг от началото до спирането на машината. Сложността на функция, изчислена от някаква машина на Тюринг, е функция, която зависи от дължината на входната дума и е равна на максималното време на работа на машината за всички входни думи с фиксирана дължина:

Ако за функцията еима машина на Тюринг Мтакъв, че за някакво число ° Си достатъчно голям н, тогава казваме, че принадлежи към класа FP или е полином по време.

P класът е един от фундаменталните в теорията на изчислителната сложност.

NP клас

Класът NP (от английския недетерминиран полином) е набор от задачи за разпознаване, чието време за решаване значително зависи от размера на входните данни; в същото време има алгоритъм, който, след като получи, заедно с описанието на входните стойности, допълнителна информация (свидетел на решението), може достатъчно бързо (за време, ненадвишаващо полинома на размера на данните) да реши проблемът.

По-формално се казва, че език L принадлежи към класа NP, ако съществува двуместен предикат R(x, y) от класа P (тоест изчислим за полиномно време) и полином p, такъв, че за всяка дума x с дължина n условието „x принадлежи на L” е еквивалентно на условието „има y с дължина, по-малка от p(n), така че R(x, y) е вярно”. Думата y се нарича свидетел, че x принадлежи на езика L. По този начин, ако имаме дума, която принадлежи на езика, и друга свидетелска дума с ограничена дължина (която може да бъде трудно да се намери), тогава можем бързо да проверим, че x наистина принадлежи на L. Всяка задача, принадлежаща на NP, може да бъде решена в експоненциално време чрез изброяване на всички възможни свидетели с дължина по-малка от p(n).

Пример за задача от NP: задачата за разпознаване "Наличие на целочислено решение на система от линейни неравенства." Свидетелят е решението на системата от неравенства. Лесно е да се провери в полиномиално време дали свидетелското решение отговаря.

Класът NP включва класа P.

Отворени проблеми

В теорията на изчислителната сложност има много нерешени проблеми, те се отнасят главно до въпросите за разделяне или влагане на определени класове сложност. Един от тези въпроси е проблемът за равенството на класовете P и NP.

Проблем за равенството на класове P и NP

В крайна сметка проблемът за равенството на класовете P и NP е следният: ако положителен отговор на някакъв въпрос може да бъде проверен бързо (в полиномиално време), тогава вярно ли е, че отговорът на този въпрос може да бъде намерен бързо (в полиномно време )?

От дефиницията на класовете P и NP непосредствено следва следствието: . Досега обаче нищо не се знае за строгостта на това включване, т.е. дали съществува алгоритъм, който е в NP, но не и в P. Ако няма такъв алгоритъм, тогава всички проблеми, принадлежащи към класа NP, могат да бъдат решени за полиномно време, което обещава огромна изчислителна полза. Сега най-трудните NP-проблеми (т.нар. NP-пълни проблеми) могат да бъдат решени за експоненциално време, което почти винаги е неприемливо.

Въпросът за равенството на тези два класа се счита за един от най-трудните отворени проблеми в областта на теоретичната информатика. В момента повечето математици смятат, че тези класове не са равни. Институтът по математика Клей включи този проблем в своя списък с проблеми на хилядолетието, предлагайки награда от един милион щатски долара за решаването му.

литература

Гери М., Джонсън Д. Изчислителни машини и трудни за решаване проблеми. Издателство „Мир” през 1982г. - 420 стр. Монографията на американски учени е посветена на решаването на сложни (включително NP-трудни) комбинаторни задачи, възникващи при дискретна оптимизация, математическо програмиране, алгебра, теория на автоматите с примери.
Кормен, Томас Х.; Лейзерсън, Чарлз I.; Ривест, Роналд Л.; Стейн, Алгоритми на Клифорд: изграждане и анализ, 2-ро издание = Въведение в алгоритмите второ издание. - М.: "Уилямс", 2005. -

Вече знаем, че коректността далеч не е единственото качество, което трябва да притежава една добра програма. Една от най-важните е ефективността, която характеризира преди всичко, преднинапрограми за различни входни данни (параметър ).

Намирането на точната зависимост за конкретна програма е доста трудна задача. Поради тази причина обикновено е ограничен асимптотични оценкитази функция, тоест описание на нейното приблизително поведение за големи стойности на параметъра. Понякога за асимптотични оценки се използва традиционната връзка (четете "Голямо О") между две функции , чието определение може да се намери във всеки учебник по математически анализ, въпреки че се използва по-често отношение на еквивалентност(прочетете "тета голяма"). Формалната му дефиниция е, например, в книгата, въпреки че засега ще ни е достатъчно да разберем този въпрос в общи линии.

Като първи пример, нека се върнем към програмите, които току-що разгледахме за намиране на факториала на число. Лесно е да се види, че броят на операциите, които трябва да бъдат извършени, за да се намери факториал! числото в първо приближение е право пропорционално на това число, тъй като броят на повторенията на цикъла (итерациите) в тази програма е равен на . В такава ситуация е обичайно да се каже, че програмата (или алгоритъмът) има линейна сложност(сложност или).

Възможно ли е да се изчисли по-бързо факториал? Оказва се, че да. Възможно е да се напише програма, която ще даде правилния резултат за същите стойности, за които всички горни програми правят, без да се използва нито итерация, нито рекурсия. Неговата сложност ще бъде , което всъщност означава организация на изчисленията по някаква формула без използване на цикли и рекурсивни извиквания!

Не по-малко интересен е примерът за изчисляване на числото на Фибоначи. В процеса на неговото изследване всъщност вече се установи, че неговата сложност е експоненциалени равно на . Такива програми практически не са приложими на практика. Това е много лесно да се провери, като се опитате да изчислите 40-то число на Фибоначи с него. Поради тази причина следният проблем е доста актуален.

Задача 5.4 линейна сложност.

Ето решение на този проблем, при което променливите j и k съдържат стойностите на две последователни числа на Фибоначи.

Текст на програмата

публичен клас FibIv1 ( public static void main(String args) хвърля изключение ( int n = Xterm.inputInt("Enter n ->< 0) { Xterm.print(" не определено\n"); } else if (n < 2) { Xterm.println(" = " + n); } else { long i = 0; long j = 1; long k; int m = n; while (--m >0) ( k = j; j += i; i = k; ) Xterm.println(" = " + j); ) ) )

Следващият въпрос е съвсем естествен – възможно ли е да се намират числата на Фибоначи още по-бързо?

След изучаване на определени раздели от математиката е доста лесно да се изведе следната формула за -то число на Фибоначи, което е лесно да се провери за малки стойности:

Може да изглежда, че въз основа на него е лесно да се напише програма със сложност, която не използва итерация или рекурсия.

Текст на програмата

публичен клас FibIv2 ( public static void main(String args) хвърля изключение ( int n = Xterm.inputInt("Enter n -> "); double f = (1.0 + Math.sqrt(5.)) / 2.0; int j = (int)(Math.pow(f,n) / Math.sqrt(5.) + 0,5); Xterm.println("f(" + n + ") = " + j); ) )

Всъщност тази програма използва извикване на функцията за експоненцииране ( Math.pow(f,n) ), която не може да бъде реализирана по-бързо, отколкото в логаритмично време (). За алгоритми, при които броят на операциите е приблизително пропорционален (в компютърните науки е обичайно да не се посочва основата на двоичния логаритъм) те казват, че имат логаритмична сложност ().

За да се изчисли числото на Фибоначи, има такъв алгоритъм, чиято софтуерна реализация ще дадем без допълнителни коментари, в противен случай трябва да обяснявате твърде много (свързване на числата на Фибоначи с мощности на определена матрица от ред два, като се използват класове за работа с матрици, алгоритъм за бързо издигане на матрица в степен) .

Задача 5.5. Напишете програма, която отпечатва -тото число на Фибоначи, което има логаритмична сложност.

Текст на програмата

публичен клас FibIv3 ( public static void main(String args) хвърля изключение ( int n = Xterm.inputInt("Enter n -> "); Xterm.print("f(" + n + ")"); if (n< 0) { Xterm.println(" не определено"); } else if (n < 2) { Xterm.println(" = " + n); } else { Matrix b = new Matrix(1, 0, 0, 1); Matrix c = new Matrix(1, 1, 1, 0); while (n>0) ( ако ((n&1) == 0) ( n >>>= 1; c.square(); ) иначе ( n -= 1; b.mul(c); ) ) Xterm.println(" = " +b.fib()); ) ) ) клас Матрица ( private long a, b, c, d; публична матрица (long a, long b, long c, long d) ( this.a = a; this.b = b; this.c = c; this.d = d; ) public void mul(Matrix m) ( long a1 = a*m.a+b*mc; long b1 = a*m.b+b*md; long c1 = c*m.a+ d *mc; long d1 = c*m.b+d*md; a = a1; b = b1; c = c1; d = d1; ) public void square() (mul(this); ) public long fib() (връщане b;))

Ако се опитате да изчислите десет милионното число на Фибоначи, използвайки тази и предишната програма, тогава разликата във времето за изчисление ще бъде доста очевидна. За съжаление, резултатът ще бъде неправилен (и в двата случая) поради ограничения диапазон от числа от типа long .

В заключение представяме сравнителна таблица на времената за изпълнение на алгоритми с различна сложност и обясняваме защо с увеличаване на скоростта на компютъра важността на използването на бързи алгоритми нараства значително.

Помислете за четири алгоритма за решаване на същия проблем със сложност , , и , съответно. Да предположим, че вторият от тези алгоритми изисква точно една минута време за изпълнение на някакъв компютър със стойността на параметъра. Тогава времената за изпълнение на всички тези четири алгоритма на един и същ компютър с различни стойности на параметъра ще бъдат приблизително същите като за 10 300 000 години

Когато начинаещите програмисти тестват своите програми, стойностите на параметрите, от които зависят, обикновено са малки. Следователно, дори ако при писане на програма е бил приложен неефективен алгоритъм, това може да остане незабелязано. Ако обаче такава програма се опита да се приложи в реални условия, тогава нейната практическа непригодност ще се прояви веднага.

С увеличаване на скоростта на компютрите се увеличават и стойностите на параметрите, за които работата на един или друг алгоритъм завършва в приемливо време. По този начин средната стойност на стойността се увеличава и следователно се увеличава стойността на съотношението на времената за изпълнение на бързите и бавните алгоритми. Колкото по-бърз е компютърът, толкова по-голяма е относителната загуба при използване на лош алгоритъм!

За сравняване на алгоритми е обичайно да се използва обобщена характеристика, наречена ефективност. Казва се, че алгоритъмът L, по-ефикасноалгоритъм А 2 ,ако алгоритъмът L се изпълнява за по-малко време и (или) изисква по-малко компютърни ресурси (RAM, дисково пространство, мрежов трафик и т.н.).

Ефикасният алгоритъм трябва да отговаря на изискванията за приемливо време за изпълнение и разумна консумация на ресурси, както вече беше споменато в раздел 1.1. Комбинацията от тези характеристики е концепцията за сложността на алгоритъма. С увеличаване на времето за изпълнение на алгоритъма и (или) включените ресурси, сложността се увеличава. По този начин понятията ефективност и сложност са обратни едно на друго.

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

При количествените и качествените оценки на алгоритъма, свързани с определяне на сложността, се използват два подхода – практически и теоретичен.

Практически подходсвързани с реално работещи алгоритми на конкретни физически устройства. Характеризира се с параметри, които могат да бъдат измерени и записани. Времевата сложност при този подход може да бъде изразена във времеви единици (например милисекунди) или в броя на процесорните цикли, необходими за изпълнение на алгоритъма. Капацитивната сложност може да бъде изразена в битове (или други единици информация), минималните хардуерни изисквания, необходими за изпълнение на алгоритъма и т.н.

Практическият резултат не е абсолютна мярка за ефективността на алгоритъма. Количествените стойности, получени с този подход, зависят от много фактори, като например:

технически характеристики на компонентите, съставляващи изчислителната система. И така, колкото по-висока е тактовата честота на процесора, толкова по-елементарни операции за единица време могат да бъдат извършени;
характеристики на софтуерната среда (брой изпълнявани процеси, алгоритъм на планировчика на задачи, характеристики на операционната система и др.);
избрания език за програмиране за реализация на алгоритъма. Програма, написана на език от високо ниво, е вероятно да работи по-бавно и да изисква повече ресурси от програма, написана на езици от ниско ниво, които имат директен достъп до хардуерни ресурси;
опит на програмиста, внедрил алгоритъма. Най-вероятно начинаещ програмист ще напише по-малко ефективна програма от опитен програмист.

По този начин, алгоритъм, работещ на една и съща компютърна система за едни и същи входни данни, може да има различни резултати в различно време. Следователно теоретичният подход към дефиницията на сложността е по-важен.

Теоретична сложностхарактеризира алгоритъма без позоваване на специфичен хардуер, софтуер и инструменти за изпълнение. В този случай времевата сложност се изразява чрез броя на операциите, циклите на машината на Тюринг и т.н. Капацитивната сложност се определя от количеството данни (входящи, междинни, изходни), броя на участващите клетки на лентата на машината Tyoring и т.н.

В теоретичния подход за оценка на ефективността се счита, че алгоритъмът се изпълнява на някои идеализиран компютър, за които времето за изпълнение на всеки тип операция е известно и постоянно. Също така се смята, че ресурсите на такъв компютър са безкрайни, така че капацитивната сложност обикновено не се определя в теоретичния подход. Като времева характеристика на сложността се избира броят на инструкциите (операциите), изпълнявани на идеализиран компютър.

Количествените оценки, получени в теоретичния подход, могат също да зависят от редица от следните фактори:

количеството входни данни. Колкото по-голям е той, толкова повече време ще отнеме за изпълнение на алгоритъма;
избрания метод за решаване на проблема. Например, за голямо количество входни данни алгоритъмът за бързо сортиране е по-ефективен от алгоритъма за сортиране с балончета, въпреки че води до същия резултат.

Времето за изпълнение на алгоритъма обикновено зависи от количеството входни данни (входен размер), което се разбира като измерението на решавания проблем. Така че, когато сортирате набор от стойности, количеството данни е броят на елементите на този набор. Когато обработвате низове, размерът на входните данни е дължината на низа.

Нека бъде P -количеството входни данни за някакъв алгоритъм. Означете с T(p)броят на инструкциите, изпълнявани на идеализиран компютър по време на изпълнението на алгоритъма, и се определя за "най-лошия случай", когато обемът на операциите е максимален.

Концепцията за "най-лошия случай" може да бъде илюстрирана с пример. Нека разгледаме алгоритъм за проверка на наличието на числов елемент в някакъв набор (масив) от числа. Ако този набор е сортиран във възходящ ред, тогава, най-общо казано, няма смисъл да проверявате елементите, разположени след първия елемент, който е по-голям от желания. В такъв случай T(p) n. Но в най-лошия случай (за произволно несортирано множество) ще трябва да прегледате всички елементи на набора. Очевидно тук T(n) = n.

Общо казано, T(p)е някаква функция на размера на входните данни П.В много случаи T(p)изразена като полином, степенна или логаритмична функция на П.

Стойностно поведение T(p)в зависимост от увеличението ПНаречен асимптотична сложносталгоритъм. Казват, че Т(н) То има ред на сложност 0(J(n))(Прочети "ОТНОСНОголям от/от П")за някакъв алгоритъм, ако има константа оти обем на данните SCHтакъв, че Yn > n 0и има неравенство Т(н) s/(n).

Този факт е написан като T(n) = 0(J(n))и означава, че за функцията T(p)има такава функция f(n)и константа с, за която, започвайки от някои n 0 ,смисъл T(p)не надвишава cf(n).

Функция f(n)представлява горната граница на стойностите на функцията T(n).Нека например T(n) = 2п А + n 2 .Чрез избор на стойности n 0= 0 и c = 5, за всеки n > n 0ние имаме T(n) = 2п А + стр 2 T(n) има ред i 4 .

Функция Т(н) се свързва с определен алгоритъм, така че често се казва, че порядъкът на сложност 0(/(n))има алгоритъм.

Казват, че T(p)То има долна граница Q(g(n))(прочетете „omega big off жот /r"), ако има константа c и количеството данни n 0такъв, че /Пи има неравенство T(n) > cg(n).

Този факт е написан като T(n) = Q(g(n)).Нека например T(n) = 2-ри 4+ n 2 .Избор на стойност c = 1, за всеки Пние имаме T(p)= 2-ро 4 + n 2 > cn A >следователно, Т(н) има долна граница i 4 .

Лесно е да се види, че редът и долната граница не са уникални за дадена функция T(n).В примерите по-горе можете да изберете /(i) като i 5 , i 6 ,... и като g(n) - i 3 , i 2 ,.... Обикновено функция с минимална степен се избира като /(i) и g(n)- с максимума.

Редът на сложност 0(/(i)) и долната граница Q(g(rc)) са функционални класове. Интуитивно Q(g"(n)) може да се разбира като клас от функции, растящи поне толкова бързо, колкото T(n).По същия начин, интуитивно 0(f(n))може да се разбира като клас от функции, растящи не по-бързо от T(n). ОТОт практическа гледна точка, когато се оценява сложността на алгоритъма, най-важният е именно класът функции 0(f(n)).Определяне на вида на функцията /(i) и е основната задача за изчисляванетеоретична сложност на алгоритъма.

За всеки алгоритъм, когато определяте степента на растеж, можете да използвате следните свойства на 0(/(n)):

1) 0(kf(ji))= 0(/(i)), където к= const. По този начин постоянният фактор във функцията не влияе върху скоростта на растеж. Например,

2) 0(J(ri)"g(n)) = 0(J(n))"0(g(ri)).По този начин редът на произведението на две функции е равен на произведението на тяхната сложност. Например,

Понякога това свойство се записва като

3) 0(/(p) + g(n))равно на доминантен(функции с максимална степен) на функции f(n) и g(n).Например,

В теорията на сложността на алгоритмите се разграничават следните класове функции на сложност:

1) постоянна сложност 0(1). Времето на работа на алгоритъма и използваните ресурси не зависят от количеството входни данни. Обикновено алгоритмите, които не съдържат цикли и рекурсивни извиквания, имат такава сложност;
2) линейна сложност 0(n).Обикновено проблемите с тази сложност са тези, при които всеки елемент от входните данни трябва да бъде обработен определен брой пъти, които не са свързани по никакъв начин с броя на обработката на други елементи;
3) логаритмична сложност 0 (log 2 w), 0 (nog 2 n).Понякога се използват и други основи на логаритъма;
4) полиномна сложност 0(i 2), 0(i 3), 0(i 4),...;
5) експоненциална сложност 2 стр., 3",....

С увеличаване на размера на входа, сложността на всеки следващ тип функция нараства по-бързо от предишния (с изключение на 0(log 2 /?)). За достатъчно голямо количество входни данни е за предпочитане да се използват алгоритми с по-малко сложност.

При количествено изчисляване на сложността първоначално се избира операция или група от операции, което е значимо за този алгоритъм (формира неговата основа). Обикновено те са сравнителни и аритметични операции. Операциите за сравнение включват проверка на стойностите на две величини (по-малко от, по-голямо от, равно на, по-малко от или равно на, по-голямо или равно на, не равно на). Те се считат за еквивалентни по отношение на времето за изпълнение. Аритметичните операции от своя страна се разделят на добавкаИ мултипликативна.Към първия (често наричан просто допълнение)включват добавяне, изваждане, намаляване или декрементиране на стойност на брояча. Към втория (наречено просто умножение)включват умножение, деление, вземане на остатъка по модул.

Събиранията са по-бързи от умноженията, така че се предпочитат алгоритми с по-малко умножения, дори ако броят на събиранията нараства пропорционално на размера на намалението на умноженията.

Операциите на целочислено умножение или деление на степен 2 се класифицират като адитивни операции, тъй като при работа с клетки от паметта те се свеждат до смяна, което е еквивалентно на операция на събиране.

След избор на значими транзакции, те се разделят на две категории:

1) операции, които пряко влияят върху сложността на алгоритъма;
2) операции, които представляват "режийни разходи" при изпълнение на алгоритъма (например разпределяне на памет за съхранение на междинни данни).

Директното изчисление или оценка на броя на извършените операции ви позволява да оцените T(n).

За да оцените реда на сложност, можете да използвате анализа на програмния код, който изпълнява алгоритъма. при което:

Алгоритмите без цикли и рекурсивни извиквания имат сложност от порядъка на 0(1). Така операциите по присвояване, въвеждане и извеждане на данни, условни конструкции имат постоянна сложност;
ако две части от програмния код имат сложност 0(J ((ri))И 0 (J 2 (n)),тогава последователното изпълнение има сложност

ако тялото на цикъла се изпълнява веднъж за всеки елемент от входните данни, тогава сложността на изпълнението на цикъла е от порядъка 0(n)0( 1) = 0(n);
редът на сложност на изпълнение на вложени цикли се изчислява от правилото за продукта 0(J x (n)f 2 (n)) = 0(/,(/?))- 0 (J 2 (ri)).Ако всеки от тях има сложност на поръчката 0(n),изпълнението на вложени цикли има сложност на поръчката 0(n 2).

Пример 1.3

Определете реда на сложност на алгоритъма на програмата в езика

Pascal, показан в листинг 1.2. Програмните редове са номерирани като коментари (вижте раздел 2.6).

Списък 1.2

(01) за i:=l до n do

(02) започват

(03) write("Въведете елемент от масива

с индекс ",i,": ");

(04) Readln(MyArray[i]);

(05) край;

(06) за i:=l до n do

(07) за j:=1 до n do

(08) започват

(09) write("Въведете елемент от масива

с индекси ", i, ",", j, " : ");

(10) Readln(MyDArray);

(11) край;

Решение

Редове 02, 05, 08, 11 не съдържат изпълними оператори, така че не се вземат предвид при определяне на поръчката.

Редове 03 и 04 имат ред 0(1). Последователното им изпълнение е от реда 0(1) + 0(1) = 0(1). По същия начин, последователното изпълнение на редове 09 и 10 има сложност 0(1).

Цикълът в редове 01-05 има сложност на поръчката На),вложени цикли в редове 06-11 - ред 0(n 2).Крайната сложност на алгоритъма е от порядъка

Оценката на сложността на алгоритъма, както време, така и ресурс, ви позволява да определите максималното и средното време за изпълнение на алгоритъма. Това е изключително важно при обработка на големи количества информация, особено в задачите за сортиране и търсене, разгледани по-долу.