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

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

Основните оценки на растежа, срещани в асимптотичния анализ, са:

• Ο (O-голям) е горната асимптотична оценка за растежа на времевата функция;
• Ω (Омега) е долната асимптотична оценка за растежа на времевата функция;
• Θ (Тета) са долната и горната асимптотични оценки за растежа на времевата функция.

Позволявам н– количество данни. След това растежът на функцията на алгоритъма f(н) може да ограничи функциите ж(н) асимптотично:

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

За нас най-голям е интересът Ο - функция. Освен това в следващите глави сложността на алгоритмите ще бъде дадена само за горната асимптотична граница.

Под фразата „сложността на алгоритъма е Ο (f(н))" предполага, че с увеличаване на количеството входни данни н, времето за работа на алгоритъма няма да се увеличи по-бързо от някаква константа, умножена по f(н).

Важни правила на асимптотичния анализ:

1. О(к*f) = О(f) е постоянен фактор к(константа) се изхвърля, защото с нарастването на количеството данни се губи значението й, например:

O(9,1n) = O(n)

1. О(f*ж) = О(f)*О(ж) – оценката на сложността на произведението на две функции е равна на произведението на техните сложности, например:

O(5n*n) = O(5n)*O(n) = O(n)*O(n) = O(n*n) = O(n 2)

1. О(f/ж)=О(f)/О(ж) – оценката на сложността на частното на две функции е равна на частното на техните сложности, например:

O(5n/n) = O(5n)/O(n) = O(n)/O(n) = O(n/n) = O(1)

1. О(f+ж) е равен на доминантата О(f) И О(ж) – оценката на сложността на сумата от функции се определя като оценка на сложността на доминантата на първия и втория член, например:

O(n 5 +n 10) = O(n 10)

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

Могат да се използват различни подходи за оценка на ефективността на алгоритмите. Най-простият е просто да стартирате всеки алгоритъм на няколко задачи и да сравните времето за изпълнение. Друг начин е да се оцени математически времето за изпълнение чрез преброяване на операциите.

Разгледайте алгоритъм за изчисляване на стойността на полином от степен н V дадена точка х.
P n (x) = a n x n + a n-1 x n-1 + ... + a i x i + ... + a 1 x 1 + a 0

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

изчисление аз-ти термин( i=1..n) изисква азумножения. И така, общо 1 + 2 + 3 + ... + n = n(n+1)/2умножения. Освен това се изисква n+1допълнение. Обща сума n(n+1)/2 + n + 1= n 2 /2 + 3n/2 + 1операции.

Алгоритъм 2- Извеждам х-s извън скобите и пренапишете полинома във формуляра
P n (x) = a 0 + x(a 1 + x(a 2 + ... (a i + .. x(a n-1 + a n x))).

Например,
P 3 (x) = a 3 x 3 + a 2 x 2 + a 1 x 1 + a 0 = a 0 + x(a 1 + x(a 2 + a 3 x))

Ще оценим израза отвътре. Най-вътрешната скоба изисква 1 умножение и 1 събиране. Стойността му се използва за следващата скоба... И така, 1 умножение и 1 събиране за всяка скоба, което.. n-1нещо. И след като изчислите най-външната скоба, умножете по x и добавете а 0. Обща сума нумножения + ндобавки = 2nоперации.

Често такава подробна оценка не се изисква. Вместо това е дадена само асимптотичната скорост на нарастване на броя на операциите с увеличаване на n.

Функция f(n) = n 2 /2 + 3n/2 + 1нараства приблизително колкото n 2 /2(отхвърляме сравнително бавно нарастващия термин 3n/2+1). постоянен множител 1/2 ние също премахваме и получаваме асимптотична оценка за алгоритъм 1, която се обозначава със специален символ O(n2)[чете се като "О, голям от квадрат"].

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

		n*log n
1	0	0	1
16	4	64	256
256	8	2,048	65,536
4,096	12	49,152	16,777,216
65,536	16	1,048,565	4,294,967,296
1,048,576	20	20,969,520	1,099,301,922,576
16,775,616	24	402,614,784	281,421,292,179,456

Ако приемем, че числата в таблицата съответстват на микросекунди, то за задача с n=1048576елементи на алгоритъма с време на изпълнение O(log n)ще отнеме 20 микросекунди, алгоритъмът във времето На)- 17 минути и алгоритъма с времетраене O(n2)- повече от 12 дни... Сега предимството на алгоритъм 2 с оценка На)преди Алгоритъм 1 е съвсем очевиден.

Най-добрата оценка е О(1)... В този случай времето не зависи от н, т.е. постоянно за произволен брой елементи.

По този начин, О()- "скъсена" оценка на времето за работа на алгоритъма, която често се получава много по-лесно от точната формула за броя на операциите.

И така, нека формулираме две правила за формиране на оценката O().

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

Когато се оценява O(), константите не се вземат предвид.
Нека единият алгоритъм направи 2500n + 1000 операции, а другият - 2n+1. И двете са оценени На), тъй като времето им за изпълнение нараства линейно.

По-специално, ако и двата алгоритъма, напр. O(n*log n)Това обаче не означава, че те са еднакво ефективни. Първият може да бъде, да речем, 1000 пъти по-ефективен. O() означава само, че времето им се увеличава приблизително като функция на n*log n.

Друго следствие от пропускането на константата е алгоритъмът във времето O(n2)може да работи много по-бързо от алгоритъма На) за малки n... Поради факта, че реалният брой операции на първия алгоритъм може да бъде n2 + 10n + 6, а второто - 1000000n+5. Вторият алгоритъм обаче рано или късно ще изпревари първия... n 2расте много по-бързо 1000000n.

Основа на логаритъм в символ О()не е написано.
Причината за това е съвсем проста. Нека имаме O(log2n). Но log 2 n=log 3 n/log 3 2, А дневник 3 2, като всяка константа, асимптотиката е символът ОТНОСНО()не взема предвид. По този начин, O(log2n) = O(log 3 n).

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

Математическа интерпретация на символа O().

Определение
O(g)- много функции f, за които има такива константи ° СИ н, Какво |f(x)|<= C|g(x)| за всички x>N.
Записване f = O(g)буквално означава това fпринадлежи към комплекта O(g). В този случай обратният израз O(g) = fняма смисъл.

По-специално може да се каже, че f(n) = 50nпринадлежи O(n2). Тук имаме работа с неточна оценка. Разбира се f(n)<= 50n 2 при n>1, но по-силно твърдение би било f(n) = O(n), защото за C=50И N=1точно f(n)<= Cn, n>н.

Други видове оценки.

Заедно с оценката На)използван резултат Ω(n)[чете се като "Омега голяма от en"]. Означава по-ниска оценка за растежа на функцията. Например, нека функцията описва броя на операциите на алгоритъма f(n) = Ω(n 2). Това означава, че дори и в най-успешния случай ще бъде произведен не по-малко от порядък. n 2действия.
...По време на оценка f(n) = O(n 3)гарантира, че в най-лошия случай действията ще бъдат наред n 3, не повече.

Използва се и оценката Θ(n)["Тета от en"], което е хибрид О()И Ω() .
Θ(n2)е едновременно горна и долна асимптотична оценка - редът n 2операции. Степен Θ() съществува само когато О()И Ω() мач и равен.

За алгоритмите за изчисляване на полинома, разгледан по-горе, намерените оценки са едновременно О(), Ω() И Θ() .
Ако добавим към първия алгоритъм за проверка за х=0в степенуване, след това върху най-успешните начални данни (когато х=0) имаме ред нпроверки, 0 умножения и 1 събиране, което дава нова оценка Ω(n)заедно със старите O(n2).

По правило основното внимание все още се обръща на горната граница О(), така че въпреки "подобрението", Алгоритъм 2 остава за предпочитане.

Така, О()- асимптотична оценка на алгоритъма върху най-лошите входни данни, Ω() - на най-добрите входни данни, Θ() - съкратено означение на същ О()И Ω() .

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

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

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

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

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

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

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

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

Оценката е сравнение с безкраен набор от функции с еднакъв ред на нарастване, различаващи се с постоянен фактор. Една функция принадлежи към множеството, ако има константи u, които за достатъчно голямо N ограничават функцията отгоре и отдолу, което описва скоростта на анализирания алгоритъм. Следователно важи следната връзка:

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

Сред типичните асимптотични оценки на изчислителната сложност на алгоритмите, следните функции са общи:

линеен O(N) (време, пропорционално на увеличението на данните);

квадратичен O(N 2);

полиномна сложност O(N M), по-специално кубична сложност O(N 3);

експоненциална сложност O(2 N);

факторна сложност O(N!);

логаритмична сложност O(log(N)) (предполага логаритъм с основа 2);

линейно-логаритмична сложност O(N * log(N)) ;

постоянна изчислителна сложност O(1) (времето не зависи от количеството данни).

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

Изчислителната сложност на разработените алгоритми трябва да бъде възможно най-ограничена. Връзката между тези оценки може да се усети чрез представяне на броя инструкции, изпълнени върху конкретни примери, да речем при N=5, 10, 25, 100 и 500 (предполагаме, че постоянните коефициенти са еднакви за по-лесно разбиране). С това количество данни получаваме следните показатели:

				толкова много	толкова много
			толкова много	толкова много	толкова много

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

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

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

Повърхностна оценка на изчислителната сложност

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

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

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

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

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

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

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

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

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

вътрфакториел( вътр _х)

ако(_х< 1)

връщане 0;

иначе ако(_x==1)

връщане 1;

връщане _x * факториел (_x - 1);

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

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

Анализ на алгоритъма –

Видове анализи

Най-лошия случай: T(n)

Среден случай: T(n)

Асимптотична оценка

О

f (n) = O(g(n))

($c > 0, n 0 >

O(g(n)) = (f (n) : $ c > 0, n 0 >

Пример: 2n2 = O(n3)

Сортиране чрез сливане

ако (стр< r) //1

Дърво на рекурсия: T(n) = 2*T(n/2) +cn, с –const, c>0

Техника за оценка на рекурсивни алгоритми.

Итерационен метод

Въз основа на формулата T(n), ние записваме формулата за по-малкия елемент, разположен от дясната страна на формулата за T(n).

Заместваме дясната страна на получената формула в оригиналната формула

Извършваме първите две стъпки, докато разширим формулата в серия без функцията T(n)

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

T(n)=T(n-1)+n, T(1)=1

T(n)=θ(g(n)), g(n)=?

T(n-1)=T(n-2)+(n-1)

T(n-2)=T(n-3)+(n-2)

T(n-3)+(n-2)+(n-1)+n=...

1+…(n-2)+(n-1)+n=

Рекурсивно дърво - графичен метод за показване на заместване на релация себе си

T(n)=2T(n/2)+n 2

T(n/4) T(n/4) T(n/4) T(n/4)

(n/2) 2 (n/2) 2 log n (1/2)*n 2

(n/4) 2 (n/4) 2 (n/4) 2 (n/4) 2 (1/4)*n 2

Метод на заместване

1. Познай (предложи) решение
2. Проверете решението с помощта на индукция
3. Намерете и заместете константи

T(n) = 2T(n/2) + n

T(n) = (n log n)

Предпоставка за индукция: T(n) ≤ с * n* log n, c>0

Нека тази оценка е вярна за n/2

T(n/2) ≤ c*(n/2)*log(n/2)

Заместете го в оригиналната формула за T(n)

T(n) ≤ 2*(c*(n/2)*log(n/2))+n ≤

c*n*log(n/2)+n =

c*n*log n - c*n*log 2 +n =

c*n*log n - c*n +n ≤

c*n*log n

c≥1, n≥2

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

T (n) = aT (n/b) + f (n), a ≥ 1, b > 1, f (n) − (f (n) > 0, n > n0)

Алгоритми за сортиране на масиви в полиномиално време

Сортиране - процес на пренареждане на обекти от дадена

агрегати в определен ред (увеличаване

или намаляваща).

Целта на сортирането обикновено е да улесни последващите

търсене на елементи в сортирано множество.

Сортиране чрез прости вмъквания

void sort_by_insertion(ключ a, int N)

за (i=1; i< N; i++)

за (j=i-1; (j>=0)&& (x< a[j]); j--)

a = a[j];

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

Брой сравнения:

C (N) \u003d 1 + 2 + 3 + ... + N - 1 \u003d (N * (N -1)) / 2 \u003d O (N 2)

Общо време: T(N) = θ(N 2)

Сортиране чрез обикновен обмен. мехурчен метод.

void bubble_sort(ключ a, int N)

за (i=0; i

за (j=N-l; j>i; j--)

if (a > a[j]) (

x = a[j] ; a [ j ] = a [ j -1] ; a[j-1]=x;

Опростен анализ на сортиране на борсата

Най-лошият случай: поръчан в обратен редмасив

Брой сравнения:

C(N) = (N - 1) + (N - 2) + ... + 1 = (N * (N-1))/2 = O(N 2)

Общо време: T(N) = θ(N 2)

Допълнение

Възел* _Добавяне (възел *r, T s)

r = нов възел(и);

иначе ако (s< r->инф)

r->left = _Add(r->left, s);

r->right = _Add(r->right, s);

Премахване на елемент от дървото

Дърво T с корен n и ключ K.

премахнете от дървото T възела с ключа K (ако има такъв).

Алгоритъм:

Ако дърво T е празно, спрете;

В противен случай сравнете K с ключа X на основния възел n.

Ако K>X, рекурсивно премахване на K от дясното поддърво на T;

Ако К

Ако K=X, тогава е необходимо да се разгледат три случая.

Ако няма и двете деца, тогава изтриваме текущия възел и нулираме връзката към него от родителския възел;

Ако едно от децата не съществува, тогава поставяме стойностите на полетата на детето m вместо съответните стойности на основния възел, презаписвайки старите му стойности и освобождавайки паметта, заета от възела m;

Ако и двете деца присъстват, тогава намираме възела m, който е следващият след дадения;

копиране на данните (с изключение на препратките към дъщерни елементи) от m в n;

рекурсивно премахване на възела m.

Елементът, следващ дадения

Дадени са: дърво T и ключ x

Връщаме указател към следващия елемент след x или NULL, ако x е последният елемент в дървото.

Алгоритъм:

Разглеждаме два случая поотделно.

Ако дясното поддърво на x не е празно, тогава следващият елемент след x е минималният елемент в това поддърво.

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

Вмъкване на възли

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

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

Премахване на възли

За да премахнете връх от AVL дърво, като основа се взема алгоритъм, който обикновено се използва при премахване на възли от стандартно двоично дърво за търсене. Намираме възела p с дадения ключ k, в дясното поддърво намираме възела min с най-малкия ключ и заместваме премахнатия възел p с намерения възел min.

Има няколко варианта за изпълнение. Първо, ако намереният възел p няма дясно поддърво, тогава, чрез свойството на AVL дървото, този възел може да има само един дъщерен възел (дърво с височина 1) отляво или възел p в общ е лист. И в двата случая просто трябва да изтриете възела p и като резултат да върнете указател към левия дъщерен възел на възела p.

Сега нека p има дясно поддърво. Намерете минималния ключ в това поддърво. По свойство на дърво за двоично търсене този ключ е в края на левия клон, започвайки от корена на дървото. Използваме рекурсивната функция findmin.

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

Хеш таблици, верижен метод

Директното адресиране се използва за малки комплекти ключове. Изисква се да се зададе динамично множество, всеки елемент от което има ключ от множеството U = (0,1,..., m - 1), където m не е твърде голямо, няма два елемента с еднакви ключове.

За представяне на динамичен набор се използва масив (таблица с директно адресиране), T, всяка позиция или клетка от който съответства на ключ от ключовото пространство U.

Клетка k сочи към елемент от множеството с ключ k. Ако множеството не съдържа елемент с ключ k, тогава Т[k] = NULL.

Операцията по търсене на ключ отнема време О(1)

Недостатъци на директното адресиране:

Ако ключовото пространство U е голямо, таблицата T се съхранява с размер |U| непрактично, ако не и невъзможно, в зависимост от количеството налична памет и размера на пространството на ключовете

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

Хеш функцията е функция h, която намира елементите на множеството U в таблицата T.

При хеширане елементът с ключ k се съхранява на място h(k), хеш функцията h се използва за изчисляване на местоположението за даден ключ k. Функцията h преобразува ключовото пространство U към клетките на хеш-таблицата T [0..m - 1]:

h: U → (0,1,...,m-1).

стойността h(k) се нарича хеш стойност на ключа k.

Когато наборът K от ключове, съхранени в речника, е много по-малък от пространството на възможните ключове U, хеш-таблицата изисква значително по-малко пространство от директно адресируемата таблица.

Целта на хеш функцията е да намали работния диапазон на индексите на масива и вместо |U| стойности, можете да преминете само с m стойности.

Изискванията към паметта могат да бъдат намалени до θ(|K|), докато времето за търсене на елемент в хеш-таблица остава O(1) - това е границата на средното време за търсене, докато в случай на таблица с директно адресиране, тази граница е валидна за най-лошия случай.

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

Например h(43) = h(89) = h(112) = k

Верижен метод:

Идея: Съхранявайте елементи от набор със същата хеш стойност като списък.

h(51) = h(49) = h(63) = i

Анализ

Най-лошият случай: ако хеш функцията за всички елементи от набора произвежда една и съща стойност. Времето за достъп е Θ(n), за |U | = н.

Среден случай: За случая, когато хеш стойностите са равномерно разпределени.

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

Нека е дадена таблица T и в нея се съхраняват n ключа.

Тогава a = n/m е средният брой ключове в клетките на таблицата.

Времето за търсене на липсващия елемент е Θ(1 + α).

Постоянното време за изчисляване на хеш стойността плюс времето за преминаване през списъка до края, защото средната дължина на списъка е α, тогава резултатът е Θ(1) + Θ(α) = Θ(1 + α)

Ако броят на клетките на таблицата е пропорционален на броя на елементите, съхранявани в нея, тогава n = O(m) и следователно α = n/m = O(m)/m = O(1), което означава, че търсенето на елемент в хеш-таблицата отнема средно време Θ(1).

Операции

Вмъкване на елемент в таблица

Премахване

също изискват O(1) време

Избор на хеш функция

Ключовете трябва да бъдат равномерно разпределени във всички клетки

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

Методи:

метод на разделяне

метод на умножение

метод на разделяне

h(k) = k mod m

Проблем с малкия делител m

Пример #1. m = 2и всички ключове са четни Þ нечетните клетки не са

запълнена.

Пример #2. m = 2rÞ хешът е независим от битовете по-горе r.

метод на умножение

Позволявам м= 2 r , ключовете са w-битови думи.

h(k) = (A k mod 2 w) >> (w - r),Където

A mod 2 = 1 ∩ 2 w-1< A< 2 w

Той не трябва да избира Аблизо до 2 w-1И 2w

Този метод по-бърз методразделение

Метод на умножение: пример

m = 8 = 2 3 , w = 7

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

Търсенето също е последователно изследване

Успех, когато намериш смисъла

Неуспех при намиране на празна клетка или преминаване на цялата таблица.

Изследователски стратегии

Линеен -

h(k, i) = (h′(k) + i) mod m

Тази стратегия е лесна за изпълнение, но е предмет на проблема

първично клъстериране, свързано със създаването на дълга последователност

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

квадратна

h(k, i) = (h′(k) + с 1 i+ с 2 i 2) mod m

където h′(k) е обичайната хеш функция

Двойно хеширане -

h(k,i) = (h 1 (k) + i h 2 (k)) mod m.

двойно хеширане

Този метод дава отлични резултати, но h 2 (k) трябва да бъде относително просто спрямо m.

Това може да се постигне:

използвайки степени на 2 като m и правейки h 2 (k) произвежда само нечетни числа

m = 2 r и h 2 (k)- странно.

м- просто число, стойности h 2 са цели положителни числа, по-малки от m

За прости м може да се монтира

h1(k)=k mod m

h2(k)=1+(k mod m')

m' е по-малко от m (m' =m-1 или m-2)

Отворете адресиране: Пример за поставяне

Нека е дадена таблица A:

двойно хеширане

h2(k)=1+(k mod 11)

Къде ще бъде вграден елементът?

Отворен адресен анализ

Допълнително предположение за равномерно хеширане е, че всеки ключ е еднакво вероятно да получи някой от m! пермутации на последователности за изследване на таблици

независимо от другите ключове.

Намиране на липсващ елемент

Брой сонди за успешно търсене

отворено адресиране

А< 1 - const Þ O(1)

Как се държи A:

Таблица завърши 50% Þ2 проучване

Таблица 90% завършена Þ 10 проучвания

Таблица 100% завършени Þ m проучвания

Принципът на алчния избор

Говори се, че за оптимизационен проблем прилагаме принцип на алчен избор, ако последователността е локална оптимални изборидава глобално оптимално решение.

В типичен случай доказателството за оптималност следва следната схема:

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

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

Аргументът завършва с индукция.

Оптималност за подзадачи

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

Изграждане на кода на Хъфман

Всяко съобщение се състои от поредица от знаци от някаква азбука. Често, за да се спести памет, да се увеличи скоростта на пренос на информация, възниква задачата за компресиране на информация. В този случай се използват специални методи за кодиране на знаци. Те включват кодове на Huffman, които дават компресия от 20% до 90% в зависимост от вида на информацията.

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

Алгоритъмът на Хъфман е пример за алчен алгоритъм.

Нека честотите на знаците са известни във файл с дължина 100 000 знака:

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

Неравномерният код ще бъде по-икономичен, ако често срещаните знаци са кодирани с кратки последователности от битове, а рядко срещаните знаци с дълги. Когато кодирате целия файл, това ще отнеме (45*1 + 13*3 + 12*3 + 16*3 + 9*4 + 5*4)*1000 = 224000. Това означава, че неравният код дава около 25% спестявания .

Префикс кодове

Помислете за кодове, в които за всяка от две последователности от битове, представляващи различни символи, нито един от тях не е префикс на другия. Такива кодове се наричат ​​префиксни кодове.

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

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

За да приложите ефективно декодирането, трябва да съхранявате информация за кода в удобна форма. Една от възможностите е да представите кода във формуляра кодово двоично дърво, чиито листа съответстват на кодираните знаци. В този случай пътят от корена до кодирания знак определя кодиращата последователност от битове: движението по дървото наляво дава 0, а движението надясно дава 1.

Вътрешните възли показват сумата от честотите за листата на съответното поддърво.

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

Оптимално префиксно кодово дърво за файл, който използва всички знаци от някакъв набор C и само те съдържат точно | C | листа, по един за всеки знак и точно | C | - 1 възли, които не са листа.

Познавайки дървото T, съответстващо на кода на префикса, е лесно да се намери броят битове, необходими за кодиране на файла. За всеки знак c от азбуката C, нека f[c] е броят пъти, в които се среща във файла, а dT(c) дълбочината на съответния му лист и следователно дължината на битовата последователност, която кодира c. След това, за да кодирате файла, ще ви трябва:

Тази стойност се нарича цена на дървото T. Необходимо е да се минимизира тази стойност.

Хъфманпредложи алчен алгоритъм, който изгражда оптимален префиксен код. Алгоритъмът изгражда дърво T, съответстващо на оптималния код отдолу нагоре, започвайки с набор от | C | листа и правене | C | - 1 сливане.

За всеки символ е дадена неговата честота f [c]. За да се намерят два обекта за сливане, се използва приоритетна опашка Q, като се използват честоти f като приоритети - двата обекта с най-ниски честоти се сливат.

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

Хъфман ° С)

1.n ←│C│ │ ° С │- мощност C

2.Q ← ° С Q - приоритетна опашка

3. за i ← 1 да се n-1

4. направи z ← Create_Node() z е възел, състоящ се от полета f, ляво, дясно

5. x ← ляво [z] ← Извадете от опашката(Q)

6. y ← надясно [z] ← Извадете от опашката(Q)

7. f[z] ← f[x] + f[y]

8. Поставете в опашка(Q, z)

9. връщане Извадете от опашката(Q) връща корена на дървото

Степен

Опашката е реализирана като двоична купчина.

Можете да създадете опашка в O(n).

Алгоритъмът се състои от цикъл, който се изпълнява n-1 пъти.

Всяка операция на опашката отнема O(log n).

Общо време на работа O(n log n).

Проблемът с изграждането на мрежа

Райони на произход: комуникационни и пътни мрежи.

дадени:набор от мрежови възли (хостове, градове).

Необходимо:изграждане на мрежа с най-малко общо тегло на ръбовете (дължина на мрежовите кабели, дължина на пътищата).

Графичен модел:мрежовите възли са графични възли, E = V2, знаем теглата на всички ръбове.

Резултат:безплатно дърво.

MOD подход за търсене

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

На всяка стъпка от алгоритъма ние дефинираме ребро (u, v), което може да бъде добавено към A, без да се нарушава това свойство. Такъв ръб ще наречем безопасен.

GenericMST(G, w)

2, докато A не е мод

3 Намерете ребро (u, v), което е безопасно за A

4 A ← A U ((u, v))

____________________________________________________________________________

Класификация на ребрата

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

2. Обратни ребра(задни ръбове) са ръбове (u,v), свързващи връх u с неговия предшественик v в дървото за първо търсене в дълбочина. Циклите на ръбове, които могат да възникнат в насочени графи, се третират като задни ръбове.

3. прави ребра(предни ръбове) са не-дървовидни ръбове (u,v), свързващи връх u с неговия наследник v в дървото за първо търсене в дълбочина.

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

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

1. бял цвятказва, че това е ръб на дърво.
2. Сивият цвят определя задния ръб.
3. Черното показва прав или напречен ръб.

Първият случай следва директно от дефиницията на алгоритъма.

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

В третия случай имаме работа с останалите ръбове, които не попадат в първия или втория случай. Може да се покаже, че ръб (u, v) е прав, ако d [u]< d [v], и перекрестным, если d [u] >d[v]

___________________________________________________________________________

Топологично сортиране

IN колона за приоритетвсяко ребро (u, v) означава, че u предхожда v

Топологично сортиранеграфиката е конструкцията на последователност a, където за всички a i и a j $(а i ,а j) Þ i< j.

Топологичният вид на насочен ацикличен граф G = (V, E) е линейно подреждане на всички негови върхове, така че ако графът G съдържа ребро (u, v), тогава u се намира преди v под това подреждане (ако графиката не е ацикличен, такова сортиране не е възможно). Топологичното сортиране на граф може да се разглежда като подреждане на неговите върхове по хоризонтална линия, така че всички ръбове да са насочени отляво надясно.

Сортирана последователност: C2, C6, C7, C1, C3, C4, C5, C8

за всеки (u във V) цвят [u] = бяло; // инициализиране

L = нов свързан_списък; // L е празен свързан списък

за всеки (u във V)

if (color[u] == white) TopVisit(u);

връщане L; // L дава окончателна поръчка

TopVisit(u) ( // започнете търсене в u

цвят[u] = сив; // маркирайте, че сте посетили

за всеки (v в Adj(u))

if (color[v] == white) TopVisit(v);

Добавете u отпред на L; // при завършване добавяте към списъка

T (n) = Θ(V + E)

Процедури

Създаване - Задаване (u)- създаване на набор от един връх u.

Намиране - Комплект (u)- намиране на множеството, към което принадлежи върхът uвръща в какъв комплектпосоченият елемент е разположен. Всъщност това връща един от елементите на набора (наречен Представителили лидер). Този представител се избира във всеки набор от самата структура на данните (и може да се промени с течение на времето, а именно след извиквания съюз).

Ако извикването Find - Set за всеки два елемента е върнало една и съща стойност, това означава, че тези елементи са в един и същи набор, в противен случай те са в различни набори.

съюз (u,v)- обединяване на набори, които съдържат върхове uИ v

Набори от елементи ще бъдат съхранени във формуляра дървета: едно дърво съответства на едно множество. Коренът на дървото е представител (лидер) на множеството.

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

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

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

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

Евристика за компресиране на пътя

Тази евристика е предназначена да ускори нещата Намиране - Задаване () .

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

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

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

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

Прилагане на евристика за компресия на пътя позволява да се постигне логаритмична асимптотика: средно на заявка

Анализ

Инициализация - O(V)

Цикълът се изпълнява V пъти и всяка операция extractMin отнема - O(logV) пъти, общо O(V logV) пъти

Цикълът for се изпълнява O(E) пъти, а на reduceKey отнема O(logV) време.

Общо време на работа - O(V log V +E logV)= O(E logV)

Свойство за най-кратък път

Позволявам p = (v 1, v 2 ..... v k)- най-краткият път от върха v 1 до върха v kв дадена претеглена насочена графа G=(U.E)с функция за тегло w: E → Rа p ij = (v i, v i+1 .....v j)- частичен път на пътя p, който излиза от върха v iдо горе vjза произволно i и j (1 ≤ i< j ≤ k). Тогава p ijе най-краткият път от върха v iДа се v i

Дейкстра (G, w, s) (

за всеки (u във V) ( // инициализация

d [u] = + безкрайност

цвят[u] = бяло

d[s] =0 // разстоянието до източника е 0

Q = new PriQueue(V) // поставя всички върхове в Q

while (Q.nonEmpty()) ( // докато не бъдат обработени всички върхове

u = Q. extractMin() // изберете u най-близо до s

за всеки (v в Adj[u]) (

if (d[u] + w(u,v)< d[v]) { // Relax(u,v)

d[v] = d[u] + w(u,v)

Q.decreaseKey(v, d[v])

цвят [u] = черен

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

Алгоритъмът на Белман-Форд завършва работата си навреме O(V*E), тъй като инициализацията в ред 1 отнема O(V) време за всяко |V| - 1 edge върви в редове 2-4 отнема O(E) време, а for цикълът в редове 5-7 отнема O(E) време. .

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

Анализ на алгоритъма –теоретично изследване на производителността на компютърните програми и ресурсите, които консумират.

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

Определя се от функцията T(n), където n е количеството входни данни

Видове анализи

Най-лошия случай: T(n)е максималното време за всякакви входни данни с размер n.

Среден случай: T(n)е очакваното време за всеки вход с размер n.

Най-добрият случай е минималното време за работа.

Асимптотична оценка

О- нотация: асимптотична горна граница

f (n) = O(g(n))

($c > 0, n 0 > 0 z 0 ≤ f (n) ≤ c g(n), n ≥ n 0)

O(g(n)) = (f (n) : $ c > 0, n 0 > 0 z 0 ≤ f (n) ≤ c g(n), n ≥ n 0 )

Пример: 2n2 = O(n3)

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

Сортиране чрез сливане

sort(А,p,r) //p - началото на масива, r - краят на масива T(n)

ако (стр< r) //1

q=(p + r)/2; // Изчисляване на средата на масив 1

сортиране (A, p, q); // сортиране на лявата страна на T(n/2)

сортиране (A,q+1,r); // сортиране на дясната страна на T(n/2)

сливане (p,q,r); //сливане на два масива в един n