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

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

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

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

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

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

Пример 1. Нека оценим времевата сложност на алгоритъма за изчисляване на факториела на положително цяло число.

Функция Факториал(x:Цяло число): Цяло число;

Var m,i: цяло число;

За i:=2 To x Do m:=ro*i;

Нека изчислим общия брой операции, извършени от програмата, когато дадена стойностх. Изявлението m:=1; се изпълнява веднъж; тялото на цикъла (в което има две операции: умножение и присвояване) се изпълнява x - 1 пъти; присвояването се извършва веднъж факторно:=m. Ако всяка от операциите се приеме за единица сложност, тогава времевата сложност на целия алгоритъм ще бъде 1 + 2 (x - 1) + 1 = 2x От това става ясно, че стойността x трябва да се приеме като параметър. . Функцията за времева сложност се оказа следната:

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

Пример 2. Изчисляване на скаларното произведение на два вектора A = (a1, a2, ..., ak), B = (b1, b2, ..., bk).

За i:=l To k Направете AB:=AB+A[i]*B[i];

В този проблем размерът на входните данни е n = 2k. Брой извършени операции 1 + 3k = 1 + 3(n/2). Тук можем да вземем V= k= n/2. Няма зависимост на сложността на алгоритъма от стойностите на елементите на векторите A и B. Както в предишния пример, тук можем да говорим за линейна зависимост на времевата сложност от параметъра данни.

Два теоретични проблема обикновено се свързват с параметъра времева сложност на алгоритъм. Първият се състои в намиране на отговор на въпроса: каква граница на стойността на времевата сложност може да бъде достигната чрез подобряване на алгоритъма за решаване на проблема? Тази граница зависи от самата задача и следователно е нейна собствена характеристика.

Вторият проблем е свързан с класификацията на алгоритмите по времева сложност. Функцията Tα(V) обикновено расте с V. Колко бързо расте? Има алгоритми с линейна зависимост на Tα от V (както беше в примерите, които разгледахме), с квадратична зависимост и със зависимост от по-високи степени. Такива алгоритми се наричат ​​полиномиални. И има алгоритми, чиято сложност расте по-бързо от всеки полином. Проблемът, който често се решава от теоретиците - изследователи на алгоритми, е следният въпрос: възможен ли е полиномиален алгоритъм за даден проблем?

Функции, които често се срещат при анализа на алгоритми:

• дневник н(логаритмично време),
• н(линейно време),
• ндневник н,
• н 2 (квадратно време),
• 2н(експоненциално време).

Първите четири функции имат нисък темп на растеж и алгоритмите, чието време на работа се оценява от тези функции, могат да се считат за бързи. Скоростта на нарастване на експоненциална функция понякога се характеризира като "експлозивна". За сравнение нека приемем, че има алгоритми, чиято сложност (броят на операциите) се отразява точно от тези функции. Нека тези алгоритми се изпълняват на компютър, работещ със скорост 10 12 операции в секунда. С въведена дължина н≤ 100 000, алгоритмите, чиято производителност се оценява от първите четири функции, ще получат отговор за малка част от секундата. За алгоритъм със сложност 2 нвремето за изпълнение се изчислява, както следва:

• н= 50 ≈ 19 минути,
• n= 60 ≈ 320 часа,
• n= 70 ≈ 37 години.

Въпрос 15=49. Последователни, циклични и рекурсивни алгоритми.

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

Пример. Изчислете обиколката на триъгълник със страни a,b,c.13

Алгоритъм за разклонена структура

На практика рядко е възможно да се представи решението на даден проблем под формата на алгоритъм.

линейна структура. Често в зависимост от някакво междинно звено

резултатите от изчисленията се извършват или върху единия, или върху другия

формули, т.е. в зависимост от изпълнението на някои булево условие

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

Алгоритъмът на такъв изчислителен процес се нарича алгоритъм

разклонена структура.

Разклоняването е контролна структура, която организира изпълнението само на

едно от двете посочени действия в зависимост от справедливостта

някакво условие.

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

Разклоняването се записва в две форми: пълно и непълно (фиг. 1 а, б).

а) пълна форма б) непълна форма

Циклични алгоритми – алгоритми, при които е необходимо многократно да се изчисляват стойности според едни и същи математически зависимости (блокови диаграми) за различни значенияколичествата, включени в тях. Използването на цикли може значително да намали обема на веригата

алгоритъм и дължината на съответната програма. Има цикли с

даден и неизвестен брой повторения. С определен брой повторения -

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

цикъл с постусловие.

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

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

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

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

– условие за прекратяване на цикъла;

- тялото на рекурсията, което включва действия, предназначени за

изпълнение при всяка итерация;

е стъпката на рекурсия, при която рекурсивният алгоритъм се самоизвиква.

Разграничете пряка и непряка рекурсия. В първия случай алгоритъмът

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

се нарича индиректно рекурсивен.

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

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

проверка за завършване на повикване или в рекурсивна дефиниция трябва

има ограничение, при което следваща инициализация

рекурсията е прекратена.

Пример за рекурсивна функция е изчисляването на факториела на число.

int factoria(int n)

if (n) връща n* factoria(n-1);

иначе върне 1;

Пример за рекурсивна процедура:

процедура Rec(a: цяло число); започнете, ако a>0 тогава Rec(a-1); writeln(a); край;

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

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

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

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

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

В трудовете на Д. Кнут е предложен следният подход за анализиране на времето за изпълнение на алгоритмите: общото време е сумата от разходите * честотата за всяка основна операция. Основните операции могат да включват събиране, умножение, деление, получаване на елемент по индекс от масив, сравняване на цели числа и т.н. Лесно е да се види, че в този случай изчисляването на оценка на времето за изпълнение на алгоритъма е доста досадно. Ето защо А. Тюринг каза, че е удобно да се използват дори груби приближения на оценките на времето за изпълнение на алгоритъма: можете да присвоите тегла на различни операции в зависимост от тяхната честота на поява по време на работата на алгоритъма и да вземете предвид само онези операции, които съответстват на най-големите тежести. Например, когато се умножават матрици, трябва да се вземат предвид само операции като умножение и запис на числа, тъй като това са най-честите операции.Имайки предвид само най-многообщи операции - първо опростяване, предложен за приблизително изчисляване на времето за изпълнение на алгоритми.

Второто опростяване е да се отхвърлят термини от по-нисък ред (т.е. термини), които допринасят малко за крайната оценка на времето за изпълнение на алгоритъма. Например (по-нататък числото N характеризира размера на входните данни),

\(1/6 N^3 + 20N + 16 \sim 1/6N^3\),

вместо \(1/6N^3\) пишат "този алгоритъм има сложност \(O(N^3)\", вместо \(3N^4\) пишат "този алгоритъм има сложност \(O(N ^4)\ )".

Дефиниция на O-голям

Казваме, че \(f\) е "по-голямо от O" на \(g\) за \(x \to x_0\), ако съществува константа \(C>0\), такава че за всички \(x\) от околността на точката \(x_0\) е в сила неравенството \(|f(x)| \leq C|g(x)|\). По-долу е дадена илюстрация на определението (оста \(x\) е размера на входните данни, оста \(y\) е времето за изпълнение на алгоритъма). Виждаме, че започвайки от определена точка, тъй като размерът на входа клони към \(\propto\) \(f(n)\) расте по-бавно от \(g(n)\) и като цяло \(g( n)\) като че ли го ограничава отгоре.

Примери. \(1 = O(N), N = O(N^2).\)

Наред с оценките под формата \(O(N)\) се използва оценката \(\Omega(N)\) (omega large). Означава по-ниска оценка за растежа на функцията. Например нека функцията \(f(N)=\Omega(N^2)\) описва броя на операциите на алгоритъма. Това означава, че дори и в най-добрия случай ще бъдат извършени поне \(N^2\) действия. Докато оценката \(O(N^3)\) гарантира, че в най-лошия случай няма да има повече от порядъка на \(N^3\) действия. Границата \(\Theta(N)\) (тета) също се използва, която е горната и долната асимптотична граница, когато\(O(N)\) и \(\Omega(N)\) съвпада.И така, \(O(N)\) е приблизителна оценка на алгоритъма върху най-лошите входни данни,\(\Omega(N)\) - при най-добрия вход,\(\Theta(N)\) е съкращение от идентичен\(O(N)\) и \(\Omega(N)\).

Оценки на времето на изпълнение за различни алгоритми

Означаваме T(N) - времето за изпълнение на алгоритъма. Нека изследваният алгоритъм има формата:

1. Комплектът инструкции включва само основни операции:

Твърдение 1;
...
твърдение k;

Тогава T(N) = T(изявление 1) + ... + T(изявление k).

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

2.if-else изявления

Ако (условие) (
последователност от твърдения 1
}
иначе(
последователност от твърдения 2
}

Тук ще бъде изпълнена или поредица от изрази 1, или поредица от изрази 2, следователно, тъй като искаме да получим най-лошата оценка на времето за изпълнение, T(N) = max(T(последователност от изрази 1), T(последователност от изрази 2)). Например, ако времето за изпълнение на последователност от изрази 1 е O(N) и последователност от изрази е O(1), тогава T(N) = O(N).

За (i = 0; i< N; i++) {
последователност от твърдения
}

защото цикълът ще бъде изпълнен N пъти, тогава последователността от изрази също ще бъде изпълнена N пъти. Ако T(последователност от изрази) = O(1), тогава T(N) = O(N)*O(1) = O(N).

4. Вложени цикли.

За (i = 0; i< N; i++) {
за (j = 0; j< M; j ++){
...
}
}

Външният цикъл се изпълнява N пъти. Всеки път, когато се изпълнява външният цикъл, се изпълнява вътрешният цикъл M.

Сега разгледайте този код:

За (i = 0; i< N; i++) {
за (j = i + 1; j< N; j ++){
последователност от твърдения
}
}

Нека да разгледаме промяната в броя на итерациите на вътрешния цикъл в зависимост от итерацията на външния цикъл.

I цикъл j (брой пъти за изпълнение)
0 Н
1N-1
2 N-2
...
N-1 1

Тогава поредицата от оператори ще бъде изпълнена N + N-1 + ... + 1 пъти. За бързо изчисляване на такива суми са полезни формули от математическия анализ, в този случай формулата

Тези. този алгоритъм ще има сложност \(O(N^2)\).

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

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

за (j = 0; j< N; j ++){

Ако времето за изпълнение на метода е \(g(N)=O(N)\), тогава \(T(N) = O(N)*O(N) = O(N^2)\).

5. Двоично (двоично) търсене.

Int l = 0;
int u = A.length - 1
intm;
докато (л<= u) {
m = l + (u - 1)/2
ако A[m]< k {
l = m+1;
}
иначе ако A[m] == k (
връщане m;
}
иначе(
u = m - 1;
}
}
връщане -1;

Двоичното търсене ви позволява да намерите индекса на числото k в сортирания масив, ако това число не е в него, тогава се връща -1. Първо сравняваме k с числото в средата на масива. Ако k е по-малко от това число, тогава трябва да го търсим в лявата половина на масива, ако е повече, тогава в дясната половина. След това k се сравнява с числото в средата на половината от масива, избран в предишната стъпка, и т.н. С всяка итерация пространството за търсене намалява наполовина. Възниква въпросът: колко итерации ще трябва да се направят в най-лошия случай (т.е. когато число, равно на k, не бъде намерено в масива и няма останали данни за сравнение).

Виждаме, че след 1-ва итерация ще има \(N/2\) данни за търсене на индекса \(k\), след 2-ра итерация ще има \(N/4\) данни, след 3-та итерация - \(N /8\) и др. Намираме броя на итерациите в най-лошия случай, ако решим уравнението \(\frac(N)(2^x)=1\). Това уравнение е еквивалентно на уравнението \(2^x=N\), следователно \(x=log_(2)(N)\) или \(x=log(N)\) (вижте дефиницията на логаритъма) . Следователно оценката на сложността на алгоритъма за двоично търсене е \(O(logN)\).

Добрата новина е, че само няколко функции са достатъчни, за да характеризират времето за изпълнение на повечето алгоритми: \(1, logN, N, NlogN, N^2, N^3, 2^N\). Графиката илюстрира различните скорости на нарастване на времето за изпълнение на алгоритъма в зависимост от размера на входните данни:

От тази графика, по-специално, може да се види, че ако времето за изпълнение на алгоритъма е "логаритмично", т.е. алгоритъмът има \(O(logN)\) сложност, тогава това е много готино, защото времето за изпълнение нараства много бавно с увеличаване на размера на входните данни, ако времето за изпълнение зависи линейно от размера на входните данни, тогава това също не е лошо, но е по-добре да не използвате алгоритми с експоненциално време на изпълнение (\(O(2^N)\)) изобщо или използвайте само върху много малки данни.

класове P и NP

Реална неотрицателна функция \(f(m)\), дефинирана за положителни цели числа на аргумента, се нарича полиномиално ограничена, ако съществува полином \(P(m)\) с реални коефициенти, така че \(f( m) \leq P( m)\) за всички \(m \in N^+\). Проблемите, за които съществуват алгоритми с "полиномиално" време на работа, принадлежат към клас P (тези проблеми обикновено се решават бързо и безпроблемно).

Формална дефиниция.Език L принадлежи към клас P тогава и само ако съществува детерминирана машина на Тюринг M, така че:

При даден вход, M завършва работата си за полиномиално време,
- за всички \(x \in L\) M дава резултат 1,
- за всички \(x\), които не принадлежат на \(L\), M връща резултат 0.

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

Разгледайте пример за задача от клас NP. Нека е даден набор от цели числа, например (-7, -3, -2, 5, 8). Изисква се да разберете дали сред тези числа има 3 числа, които в сбора дават 0. В този случай отговорът е „да“ (например такава тройка са числата (-3, -2,5). Тъй като размерът на наборите от цели числа се увеличава, броят на подмножествата, състоящи се от 3 елемента, нараства експоненциално. Междувременно, ако ни е дадено едно такова подмножество (нарича се още сертификат), тогава можем лесно да проверим дали сумата от неговите елементи е равно на 0.

Официална дефиниция:

Език L принадлежи към класа NP тогава и само ако има полиноми \(p\) и \(q\) и детерминистична машина на Тюринг M, така че:

За всяко \(x,y\) машината M на входа \((x,y)\) работи за време \(p(|x|)\),
- за всеки \(x \in L\) има низ \(y\) с дължина \(q(|x|)\), така че \(M(x,y)=1\),
- за всеки \(x\) извън \(L\) и всички низове с дължина \(q(|x|)\) \(M(x,y)=0\).

Редуцируемост на полиномили сводимост на Карп. Функция \(f_1\) се редуцира до функция \(f_2\), ако съществува функция \(f \в P\), такава че за всяко \(x\) \(f_(1)(x)=f_( 2 )(f(x))\).

Проблем Т се нарича NP-пъленако принадлежи към класа NP и всяка друга задача от NP се свежда до него за полиномиално време. Може би най-известният пример за NP-пълен проблем е проблемът SAT (задоволимост). Нека е дадена формула, съдържаща булеви променливи, оператори "И", "ИЛИ", "НЕ" и скоби. Проблемът е: възможно ли е да се присвоят стойности на всички променливи, които се срещат във формула? лъжаИ вярнотака че формулата да приема стойността " вярно".

Проблем Т се нарича NP-твърд, ако съществува NP-пълна задача за него, която се редуцира до T за полиномиално време. Тук имаме предвид редуцируемостта на Кук. Намаляването на проблема \(R_1\) до \(R_2\) според Кук е алгоритъм с полиномиално време, който решава проблема \(R_1\), при условие че функцията, която намира решението на проблема \(R_2\) му се дава като оракул, тоест достъпът до него отнема само една стъпка.

Ето възможните връзки между горните класове проблеми (учените все още не са сигурни дали P и NP са еднакви).

Със сигурност често сте срещали означения като 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) . Например, за да определите стойността на третия елемент от масив, не е необходимо да помните елементите или да ги итерирате няколко пъти. Винаги трябва само да изчакате третия елемент във входния поток от данни и това ще бъде резултатът, чието изчисляване за произволно количество данни отнема същото време.

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

Глава 2. Сложност на алгоритмите.

2.1 Времева и изчислителна сложност на алгоритмите.

Времева сложност на алгоритъма (T(н) , Където н– размер на задачата) е времето за изпълнение на алгоритъма, измерено в стъпки (инструкции на алгоритъма, които трябва да бъдат изпълнени, за да се постигне резултатът). Тоест, това е броят на елементарните операции, които съставляват алгоритъма за решаване на проблема (:=,<>, =, +, –, *, /; и, или, не, xor; обаждане, връщане).

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

https://pandia.ru/text/78/183/images/image002_151.gif" width="178 height=60" height="60">

Случва се T(н)= ° С* н2 приложим за квадратна матрица.

Елементарните операции в случая са комбинацията от "+" и "*".

Ако оригиналната матрица е идентичност, тогава получаваме най-добрия случай.

Ако половината от елементите в матрицата са 0, половината са 1, тогава получаваме средния случай.

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

2.2 Ои Ω са означения.

Естеството на поведението на времевата сложност при нарастване н (н® ¥ ) Наречен асимптотична сложност на алгоритъма.

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

T(н)= О(н2 )= О(f(н)),

Това означава, че има положителни константи ° С, n0=конст (° С>0), такъв, че за всички н ³ н0 неравенството

T(н) £ ° С* f(н)

Това е горната граница на оценката на сложността.

Пример 2:

Позволявам T(0)=1, T(1)=4, …, T(н)=(н+1)2, тогава времевата сложност на този алгоритъм има ред на нарастване T(н)= О(н2 ).

Може да се докаже, че за всички н > н0 при н0 = 1, ° С = 4 неравенство (1) е в сила.

(н+1)2 £ 4* н2

Пример 3:

Ако времевата сложност се запише като полином

T(н)= ° С1 н2 + ° С2 н+ ° С3 ,

тогава такъв алгоритъм има порядък на сложност, който е кратен на степента на максималния елемент на полинома, тъй като расте най-бързо за н® ¥ :

T(н)= О(н2 ).

Например:

3 н2 +5 н+1 £ 5 н2

" н ³ 1

Пример 4:

Ако някой алгоритъм има сложност, кратна на 3 н, тогава може да се покаже, че редът на нарастване на скоростта не може да бъде кратен на О(2 н):

T(н)=3 н¹ О(2 н).

Нека има константи ° С, н0 , така че е в сила следното неравенство:

3н £ ° С*2 н, н > н0 .

От тук получаваме:

СЪС³ (3/2)2, н > н0 .

Но при н® ¥ няма такава константа СЪСкоето удовлетворява това неравенство.

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

T(н) ³ У(f(н))

Неравенство (2) предполага, че има някаква константа СЪС, за което н® ¥ времева сложност

T(н) ³ ° С* f(н).

Като се има предвид трудността за точно определяне на T(N) (асимптотична времева сложност), в зависимост от размера на първоначалните данни, на практика се използват долни и горни граници на времевата сложност на алгоритъма:

T(н) = р (f(н))

В зависимост от стойността на константата СЪСскоростта на нарастване на сложността на алгоритъма може да варира значително.

Пример 5:

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

T(N)=3n2 –100n+6=O(n2)

3n2 >3n2 –100n+6, n³ 1, С=3.

Ако C1» 0 (С1=0,00001), тогава неравенството

10-5 н2 > 3 н2 –100 н+6, н³ 1

не се изпълнява.

Но може да се покаже, че редът на нарастваща сложност

3n2 -100n+6¹ НА).

C*N< 3N2, N>° С.

3n2 –100n+6=(n2)

° С=2.29, н ³ н0.

2.99* н2 < 3 н2 –100 н+6

Може да се покаже, че долната граница

3 н2 –100 н+6 ¹ У(н3 ) при C=1.

Неравенство 3 н2 –100 н+6 ³ н3 не се изпълнява.

3 н2 –100 н+6= У(н)

° С1 = , н> н0 .

https://pandia.ru/text/78/183/images/image007_89.gif" width="305" height="247 src=">

f1 (н)=100 н2

f2 (н)=5 н3

н0 =20 – критична точка.

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

0 "style="margin-left:5.4pt;border-collapse:collapse;border:none">

н!

Пример 6:

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

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

Нека са дадени пет алгоритъма за решаване на една и съща задача със сложност:

A1: 100 н

A2: 100 н* logN

A3: 10 н2

A4: н3

A5: 2 н

След това за проблеми с н=2 ¸ 9 A5 ще бъде по-бърз ( f(н) ~ 4 ¸ 512 ). Други алгоритми при заместване ще дадат значително по-ниски скорости.

При н=10 ¸ 58 A3 е за предпочитане.

При н=59 ¸ 1024 A2 ще бъде най-ефективният.

При н>1024 A1 е за предпочитане.

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

Правило за сумата : Нека програмата се състои от два последователно изпълнявани алгоритъма Р1 и Р2, за които са определени сложностите О(f(н)) И О(ж(н)) съответно. Тогава времевата сложност на цялата програма ще бъде определена като сбор от времевата сложност на всеки от алгоритмите:

T(н) = T1 (н)+ T2 (н)

Като цяло получаваме:

T(n)Þ O(макс. f(n), g(n))

Правило за произведения на изкуството: Нека времевата сложност на програма, състояща се от два паралелно изпълняващи се алгоритъма от порядъка на сложност О(f(н)) И О(ж(н)) съответно се дефинира като произведение на времевата сложност на всеки от алгоритмите:

T(н) = T1 (н)* T2 (н)

Общо взето:

T(н) Þ О(f(н)* ж(н))

Логаритми.

2.3. Рекурсия.

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

f(н) Þ f(н* f(н-1))

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

Общо взето T(н) ~ О(н).

Други рекурсивни алгоритми обикновено имат времева сложност T(н) ~ О(ан) , Където а= конст, което води до обща сложност, по-голяма от сложността на нерекурсивен алгоритъм за решаване на същия проблем.

2.4 Оценка на сложността на алгоритми и програми.

2.4.2 Алгоритми за възстановяване на зависимости.

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

За да изградите аналитична зависимост на сложността на програмата, оценете функцията T(н) на някакъв интервал [ Nмин, Nмакс] . След това намерената крива на някаква аналитична функция се апроксимира с промяна на параметрите на функцията и оценка на грешката на апроксимацията.

Като правило като такава функция се използват добре познатите функции за времева сложност: О(н!), О(XN), О(NX), О(logN), О(https://pandia.ru/text/78/183/images/image010_72.gif" width="307" height="225 src=">В резултат на експеримента върху програмата беше получена таблица на времевата сложност получено:

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

https://pandia.ru/text/78/183/images/image012_68.gif" width="321" height="143 src=">

Пример 2:

Често се случва времето за изпълнение на един и същ алгоритъм, освен размера на задачата, да се влияе от други параметри, въведени от потребителя.

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

Вложен труд" href="/text/category/trudoemkostmz/" rel="bookmark"> вложен труд (работно време).

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

За един алгоритъм се казва, че е полиномиален, ако времето му на изпълнение, т.е. времевата сложност, е ограничено отгоре с полином от някаква степен T(н)= О(Nm) . Тогава всички проблеми, които се решават с такъв алгоритъм, образуват P-клас задачи. Казват, че тези задачи са включени в R.

Проблеми, чиято времева сложност е експоненциална ( T(н)= О(Кн) ), не са включени в R.

Коментирайте : Може да се покаже, че проблемите с линейна сложност са включени в P

T(н)= О(н1 )

Нека въведем клас от NP-проблеми, които могат да бъдат решени за полиномиално време с помощта на недетерминиран алгоритъм.

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

IN недетерминиран алгоритъм (NDA) за всяко дадено състояние може да има повече от едно валидно следващо състояние, т.е. такъв алгоритъм може да изпълни повече от един оператор във всеки даден момент.

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

Пример:

Детерминиран алгоритъм (DA) би решил този проблем последователно (изброяване на всички опции, сравнение с критерия за оптималност K0, докато не избере алтернативата A0).

NDA може едновременно (успоредно) да получи всички алтернативи и да сравни с K0, като се копира във формата отделен процесза всяка алтернатива, която работи независимо.

В този случай, ако някое копие установи, че е получен неправилен резултат или резултатът не е получен, то спира изпълнението си. Ако копието намери решение, което удовлетворява K0, то обявява успех и всички други копия спират да работят.

Че. NDA се характеризира с три параметъра:

1. изборе многозначна функция, чиито стойности са елементи от множеството S;

2. провалкара копието на алгоритъма да спре да работи;

3. успехкара всички копия на алгоритъма да спрат да работят и да произведат резултат.

Очевидно няма физическо устройствоне е способен на неограничено недетерминирано поведение, така че NDA е теоретичен метод.

Проблеми, които могат да бъдат решени с помощта на полином NDA, образуват клас от NP-проблеми.

2.5.2 НП- трудно иНП- пълни задачи.

Задачата, включена в R, е НП-труден, ако има полином DA (PDA) на неговото решение, който може да се използва за получаване на решение на всички задачи, включени в NP. Тоест такъв проблем е NP-труден, ако е поне толкова труден, колкото всеки проблем в NP.

Извиква се NP-трудна задача, принадлежаща на NP НП- пълензадача. Такива проблеми са не по-малко трудни от всеки проблем от NP. Освен това съществуването на PDA за NP-труден или NP-пълен проблем означава, че класовете P и NP съвпадат, т.е. възможно е да се решат всички проблеми от 3-ти клас чрез бърз алгоритъм.

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

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

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

Определение 1: Задача P1 се преобразува в задача P2, ако има такава специален случайпроблем P1 може да се трансформира за полиномиално време в някакъв специален случай на проблем P2. Тогава решението P1 може да бъде получено за полиномиално време от решението на частен случай на задачата P2.

https://pandia.ru/text/78/183/images/image024_39.gif" width="158 height=56" height="56">

Например:

f2 (xi)=(х1 Ú х2 ) Ù ( ) Ù ()

не е осъществимо, защото за всеки xi f2 (xi)= невярно.

Теорема :

Проблемът за удовлетворимост е NP-пълен.

xi избор (вярно, невярно)

ако E(x1, x2, …, xN), тогава успех

иначе се провалят

Използвайки трансформацията на проблем P1 в P2, може да се покаже, че дори ограниченият случай на проблема за удовлетворимост е NP-пълен.

К-осъществимост .

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

Минималният случай е K=3. За булева функция, представена в CNF, може да се намери функцията в полиномиално време E*(x2), съдържащ не повече от три променливи във всяка клауза. Тогава дизпълнимо, ако е възможно E*.

д* (х1 , х2 ,…, xn) ® д* (xi)

За да направим това, използваме метода за намаляване на реда на дизюнкта

(а1 Ú а2 Ú … Ú ак)=(а1 Ú а2 Ú z) Ù (а3 Ú а4 Ú … Ú ак Ú )

Чрез прилагане на итеративен процес на разлагане може да се получи E*.

Намерете алгоритъм за решение E*по-лесно от функциите д. Но в същото време доказвайки осъществимостта E*, докажете осъществимостта оригинална функция д.

Специален случай: при K=2 функцията двключен в R.

Примери за проблеми от клас NP също могат да служат като задачи върху графики :

1) Определяне на максималните клики на неориентиран граф (NP-трудна задача).

2) Проблемът за определяне на пълен подграф (NP-пълен проблем).

3) Определяне на върховото покритие на мощност L за неориентиран граф (NP-пълна задача).

4) Определяне на максималните върхови покрития на неориентиран граф (NP-трудна задача).

5) Проблемът за определяне съществуването на Хамилтонов цикъл за граф (NP-пълен проблем).

6) Проблемът на пътуващия търговец: определяне на оптималното движение по граф с едно появяване във всеки връх (NP-труден проблем).

7) Проблем с планирането (NP-пълен проблем).

2.6 Алгоритмично неразрешими проблеми

Споделете проблеми единиченИ масивна.

Например:

5+7=? е единичен проблем.

x+y=? е огромен проблем.

Фундаментално неразрешими трябва да бъдат алгоритми за получаване на обекти, които са парадоксални, или решаване на проблеми, които предполагат съществуването на парадоксални обекти.

Например, парадоксите са:

Пример 1:

10-та задача на Хилберт.

Д. Хилберт през 1901 г., когато решава диофантовите уравнения, излага проблем, който гласи:

Намерете алгоритъм, който определя някакво цяло число за произволно диофантиново уравнение

Е(х, г, …)=0

Това е полином с цели показатели и цели коефициенти за неизвестни

anxn+an-1xn-1+…+a2x2+a1x+a0=0

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

През 1970 г. ленинградският математик Ю. Матиясевич математически доказва алгоритмичната невъзможност за решаване на диофантово уравнение в общ вид.

Пример 2:

Теорема на Ферма:

Няма такива цели числа а, b, s, n (н>2) , за които равенството

ан + млрд = cn

Тази теорема е доказана за много стойности ни проверени за конкретни случаи, но все още не е създадено общо доказателство на теоремата.

Пример 3:

Проблемът с Голдбах.

Х. Холбах формулира проблема в писмо до Ойлер през 1742 г.:

Докажете, че всяко цяло число н³ 6 може да се представи като сбор от три прости числа

н= а+ b+ ° С

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

Ойлер предлага често срещано решение на този проблем: за дори нтози проблем е разрешим и е еквивалентен на разлагане на два прости термина.

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

Обозначаване	Интуитивно обяснение	Определение
	fограничен отгоре с функция ж	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/101/eebfe73c29ff3f9bc886d263bd3e91f3.png" border="0"> или style="max-width: 98%; височина: автоматично; ширина: автоматично;" src="/pictures/wiki/files/100/d96907f9d7419a7e0c74e4089c35c35e.png" border="0">
	fограничен отдолу от функцията ж(до постоянен фактор) асимптотично	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/48/0fda981f377ae7b8d361f58ce148c173.png" border="0">
	fограничена отгоре и отдолу с функция жасимптотично	0), n_0: \за всички (n>n_0) \; |Cg(n)|
	ждоминира fасимптотично	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/49/176ce786e936badb831a0bb87f25249d.png" border="0">
	fдоминира жасимптотично	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/53/554bc3f42cfa6d0638722e58e4a99d8b.png" border="0">
	fе еквивалентно на жасимптотично

Примери

Забележки

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

Ако решението на някаква задача за n-върхов граф с един алгоритъм отнема време (брой стъпки) от порядъка на n C , а с друг - от порядъка на n+n!/C, където C е постоянно число , тогава според "полиномиалната идеология" първият алгоритъм е практически ефективен, а вторият не е, въпреки че например при C = 10 (10 10) ситуацията е точно обратната.

1. Ефикасни, но сложни алгоритми може да не са желателни, ако готови програмище подкрепя лица, които не са участвали в писането на тези програми. Да се ​​надяваме, че основните положения на технологията за създаване на ефективни алгоритми са широко известни и доста сложните алгоритми се прилагат свободно на практика. Необходимо е обаче да се предвиди възможността ефективни, но "сложни" алгоритми да не бъдат търсени поради тяхната сложност и трудностите, които възникват, когато се опитвате да ги разберете.
2. Има няколко примера, когато ефективни алгоритмиизискват толкова големи количества машинна памет (без възможност за използване на по-бавни външни носители за съхранение), че този фактор отрича предимството на "ефективността" на алгоритъма.
3. При числените алгоритми точността и стабилността на алгоритмите са не по-малко важни от тяхната времева ефективност.

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

Класът на сложност е набор от проблеми за разпознаване, за които има алгоритми, които са сходни по изчислителна сложност. Двама важни представители:

Клас П

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

известни учени

• Леонид Левин
• Александър Разборов
• Еди Шеймир

Вижте също

Връзки

• Юрий Лифшиц "Съвременни проблеми на теоретичната информатика". Курс на лекции по алгоритми за NP-трудни задачи.
• А. А. РазборовТеоретична компютърна наука: гледна точка на математика // Компютъра. - 2001. - № 2. (алтернативна връзка)
• А. А. РазборовЗа сложността на изчисленията // Математическо образование. - МЦНМО, 1999. - № 3. - С. 127-141.

Фондация Уикимедия. 2010 г.

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

времева сложност (на алгоритъма)- - Теми защита на информация EN времева сложност ... Наръчник за технически преводач

КОМПЛЕКСНОСТ НА ОПЕРАТОРСКИТЕ ДЕЙНОСТИ- съвкупност от обективни фактори, влияещи върху качеството и продължителността на изпълнението от дадено лице на необходимите функции в HMS. Така. се разделя на няколко вида, всеки от които се характеризира с комбинация от фактори по определен начин ... ... Енциклопедичен речник по психология и педагогика

Изчислителна функция, която дава числена оценка на трудността (тромавостта) на процесите на прилагане на алгоритъма към първоначалните данни. Усъвършенстването на А. с. изчисленията е концепцията за сигнализираща функция (или просто сигнализираща) функция, на ръба е дадена ... ... Математическа енциклопедия

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

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

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

Алгоритъмът за сортиране е алгоритъм за подреждане на елементите в списък. В случай, че даден елемент от списък има множество полета, полето, което служи като критерий за подреждане, се нарича ключ за сортиране. На практика числото често действа като ключ, а в ... ... Wikipedia

- (GM) криптографска система с публичен ключ, разработен от Шафи Голдвасер и Силвио Микали през 1982 г. GM е първата вероятностна схема за криптиране с публичен ключ, която е доказано защитена при стандартни криптографски ... ... Wikipedia Прочетете повече