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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

O(5n/n) = O(5n)/O(n) = O(n)/O(n) = O(n/n) = O(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, конструкция х V дадена степенпоследователно умножение и след това умножете по коефициента. След това добавете условията.

Изчисляване азти термин( 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(n 2)[чете се като "O big from en square"].

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

		*nlog 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(n 2)- повече от 12 дни... Сега предимството на алгоритъм 2 с оценка На)преди Алгоритъм 1 е съвсем очевиден.

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

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

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

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

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

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

Друго следствие от пропускането на константата е алгоритъмът във времето O(n 2)може да работи много по-бързо от алгоритъма На) за малки 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(n 2). Тук имаме работа с неточна оценка. Разбира се 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"], което е хибрид О()И Ω() .
Θ(n 2)е както горна, така и долна асимптотична оценка едновременно - тя винаги ще се поддържа от порядъка на n 2операции. Степен Θ() съществува само когато О()И Ω() съвпадат и са равни на тях.

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

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

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

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

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

Оценка на асимптотична сложностобозначава се с гръцката буква Θ (тета).

f(n) = Θ(g(n)), ако съществуват c1, c2>0 и n0, така че c1*g(n)<=f(n)<=c2*g(n) , при n>n0.

Функцията g(n) е асимптотично точна оценка на сложността на алгоритъма - функцията f(n), горното неравенство се нарича асимптотично равенство, а самото обозначение Θ символизира набора от функции, които растат „колкото бързо“ като функцията g(n) - т.е. до умножение по константа. Както следва от горното неравенство, оценката Θ е едновременно горна и долна оценка на сложността. Не винаги е възможно да се получи оценка в тази форма, така че горната и долната оценка понякога се определят отделно.
Горен резултат за трудностобозначава се с гръцката буква Ο (омикрон) и е набор от функции, които растат не по-бързо от g(n).
f(n)= Ο(g(n)), ако има c>0 и n0 такива, че 0<=f(n)<=cg(n), при n>n0.
По-нисък резултат за трудностсе обозначава с гръцката буква Ω (омега) и е набор от функции, които растат не по-бавно от g(n).
f(n)= Ω(g(n)), ако има c>0 и n0 такива, че 0<=cg(n)<=f(n), при n>n0.
Като следствие: асимптотична оценка съществува само ако долната и горната граница на сложността на алгоритъма съвпадат. В практиката на анализиране на алгоритми оценката на сложността най-често се разбира като горна оценка на сложността. Това е съвсем логично, тъй като най-важното е да се прецени времето, за което алгоритъмът гарантирано ще свърши работата си, а не времето, в което със сигурност няма да свърши.

($APPTYPE CONSOLE)

използва
SysUtils;
var n:Integer;
функция резултат(n:цяло число):Цяло число; //формирането на света
var i:Цяло число;
започвам
резултат:=0;
за i:= 2 до n div 2 do
ако n mod i =0 тогава
резултат:=резултат+1;
край;

започвам
четене(n); // твоето име
запис (резултат (n));
readln;
readln;
край.
край.

4. Рекурсия със запаметяване (прозрачна версия на динамичното програмиране). Пример за бързо изчисляване на биномни коефициенти по формулата C(n,m)=C(n-1,m)+C(n-1,m-1)

Има начин да се реши проблемът с повтарящите се изчисления. Очевидно е - трябва да запомните намерените стойности, за да не ги изчислявате отново всеки път. Разбира се, това ще изисква активно използване на паметта. Например, рекурсивен алгоритъм за изчисляване на числата на Фибоначи може лесно да бъде допълнен с три „реда“:

създаване на глобален масив FD, състоящ се от нули;

след като изчислите числото F(n), поставете стойността му във FD[n];

в началото на рекурсивната процедура проверете дали FD[n] = 0 и, ако е така, върнете FD[n] като резултат, а в противен случай продължете с рекурсивното изчисление на F(n).

(Функция в Паскал)

функция C(m, n:Byte):Longint;

Ако (m=0) или (m=n)

Друго C:=C(m, n-1)+C(m-1, n-1)

(Процедура в Pascal)

Процедура C(m, n: байт; Var R: Longint);

Var R1, R2: Longint;

Ако (m=0) или (m=n)

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

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

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

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

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

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

($c > 0, n 0 >

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

Пример: 2n 2 = O(n 3)

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

ако (стр< 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

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

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

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) = 1 + 2 + 3 + ... + N - 1 = (N * (N -1))/2= 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, тогава T[k] = NULL.

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

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

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

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

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

При хеширане елемент с ключ k се съхранява в клетка h(k), хеш функцията h се използва за изчисляване на клетката за даден ключ k. Функцията h преобразува ключовото пространство U върху клетките на хеш-таблицата T [O..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 = 2 rÞ хешът не зависи от битовете по-горе 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) + c 1 i+ c 2 i 2) mod m

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

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

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

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

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

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

използвайки 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 = V 2, знаем теглата на всички ръбове.

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

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

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

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

GenericMST(G, w)

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

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 може да бъде модифициран, така че да класифицира ръбовете, срещани по време на работа. Ключовата идея е, че всеки ръб (u, v) може да бъде класифициран с помощта на цвета на връх v, когато се изследва за първи път (въпреки че правите и напречните ръбове не се различават).

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

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

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

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

___________________________________________________________________________

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

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

Топологично сортиранеграфиката е конструкцията на последователност a, където за всички a i и a j важи следното: $(a i ,a 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 до върха vkв дадена претеглена насочена графа G = (U. E)с функция за тегло w: E → Rа p ij = (v i, v i+1 .....v j)- частичен път от пътя p, който излиза от върха v iдо горе v jза произволно 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 преминаване по ръбовете в редове 2-4 отнема O(E) време, а изпълнението на for цикъла в редове 5-7 отнема O(E) време. .