Анализът на алг.е ключът към пълноценно-то им разбиране,за да мд ги прилагаме ефективно към практически зад.Той играе роля във всяка стъпка от процеса на конст-руиране и писане на алг.Една от първите стъпки,за да разберем поведението на алг е да направим емпиричен анализ.Напр.ако имаме два алг за решаване на една и съща задача,изпълняваме ги и двата,за да видим кой работи по-бавно.Когато обаче емпирич изследвания почнат да отнемат повече вре-ме,се нуждаем от матем.анализ.Осн.причи-ни,за да извърш. матем анализ на алг. са
-за да сравн разл.алг. за една и съща задача
Това прави възможно да се предвиди точно колко дълго ще работи дадена програма, или дали дадена програма ще работи по-добре от друга при опр обстоятелства. Матем.означения,които се срещат във фор-мулите,описващи поведението на алг са:
0 1 1 2 3 5 8 13 21 34 55 ...
Базовите правила в анализа на алг. са:
b)T1(N)*T2(N)= O(f(N) * g(N)).
Анализът на алг.е ключът към пълноцен-ното им разбиране,за да мд ги прилагаме ефективно към практ.зад.Той играе роля във всяка стъпка от процеса на конструи-ране и писане на алг. За да мд се извърши анализа точно е необх да знаем някои базови правила: - например при вложени цикли оценката на анализа е пропорционална на квадрата на вложените цикли. Пр.:
&a)
{ int maxSum = 0;
for( int I = 0; I < a.size(); I++)
for( int j = I; j < a.size(); j++)
{ int thisSum = 0; //O(1*N*N*N) = O(N^3)
for( int k = I;k < j;k++) //N-1 N-1 N-1
thisSum += a[k]; *1
if( thisSum > maxSum) //i=0 j=0 k=i
maxSum = thisSum; }
return maxSum;}
2. премахваме третия for:
int maxSubSum2( const vector & a)
{ int maxSum = 0;
for (int I = 0; I < a.size(); I++)// натрупваме
{int thisSum = 0;// сумата като сме я нули- //рали в началото на всеки външен for: т.е for( int j = I; j < a.size(); j++) j i-1
{ thisSum += a[j];
if( thisSum > maxSum) //Ак=Aj +Ak k=I k=i
maxSum = thisSum;}}
return maxSum; } // O(N^2)
3. divide& conquer стратегия:
цепим проблема на 2 части и т. н. рекурсивно. Съединяваме двете решения.
Max сума може да е на 3 места:
I пол.от числа II пол.от числа
4 - 3 5 - 2 -1 2 6 -2
6 8
11
int maxSumRec
( const vector< int> &a, int left, int right)
{ if( left == right) // базов случай
if( a[left]) > 0) return a[left];
else return 0;
int center = (left + right ) / 2;
int maxLeftSum =
maxSumRec( a, left, center); // T(N/2)
int maxRightSum =
maxSumRec( a, center + 1, right); // T(N/2)
int maxLeftBorderSum=0; leftBorderSum = 0;
for( int I = center; I > = left; I--)
{ leftBorderSum += a[I];
if(leftBorderSum > maxLeftBorderSum) maxLeftBorderSum = leftBorderSum }
int maxRightBorderSum = 0;
rightBorderSum = 0; // O(N)
for( int j = center + 1; j < right; j++)
{ rightBorderSum +=a[j];
if(rightBorderSum > maxRightBorderSum)
maxRightBorderSum = rightBorderSum; }
return max3(maxLeftSum, maxRightSum, MaxLeftBorderSum+maxRightBorderSum);}
int maxSubSum3 (const vector &a)
{ return maxSumRec( a,0, a.size() – 1); }
анализ (както Фибоначи):
нека T(N) за N числа; за N = 1 -> T(1) = 1;
при N>1 имаме 2рекурсии.Всеки for->O(N)
=> T(N) = 2 T(N/2)+O(N) 2T(N/2) + N
ако N=2^к T(N)=N*(k+1) T(2) = 4 = 2*2
=NlogN=O(NlogN) T(4) = 12 = 4*3
T(8) = 32 = 8*4
T(16)=80=16*5
ако N != 2 ^к -анализът е по-тежък,но резултатът е същия.
4. линейно време
int maxSubSum4 ( const vector &a)
{int maxSum = 0; thisSum = 0;
for( int j = 0; j < a.size(); j++)
{ thisSum += a[j];
if( thisSum > maxSum)
maxSum = thisSum;
else if( thisSum < 0)
thisSum = 0; }
return maxSum; }
Oтриц. ч-ло или сума едва ли е част от търсена подредица. Mд скочим към i+1 и дори към j+1. Запазили сме докъде е стигнало j.
а)всеки момент алгоритъмът дава реш. до което е стигнал (on-line алгоритми)
б)не изисква много памет.
10. логаритми в анализа. бинарно търсене, Евклидов алгоритъм за НОД, повдигане на степен. Анализ.
log в анализа на алг.Осн.алг.в тази гр: двоично търсене,алг.на Евклид за НОД, повдигане на степ.Прог.реализ.на алг. Анализ и изработ.на оценъч.формула √
Един алг.е O(logN) ако изисква const време O(1) за разделяне задачата на половинки, както и за обработката на частите е необх const време – O(N).
Методът разделяй и владей се базира на идеята,че един обект се разделя на части и рекурсивно се намира реш.за всяка част и оттук за целия обект.
Друг пример за такъв алг.двоично търсене:
Търсим X в сорт.редица A0, A1, …An-1.
Сравн.Х със средния елем.на сорт.редица и ако са равни,това е Х,ако Х<Аср,прилагаме метода за лява пол.,ако Х>Аср – за дясната
int low = 0, high = a.size() – 1;
while( low <= high)
{int mid = ( low + high) / 2;
if( a[mid] < x) low = mid + 1;
else if( x < a[ mid]) high = mid – 1;
else return mid; //открито
} return NOT_FOUND; }
O(1) вътре във всеки цикъл.
Циклите са:log( N – 1 ) + 2. => O(log(N))
Евклидов алг. за НОД( М, N) M >= N
Базиран е на наблюдението, че НОД на 2 цели числа Х и У,Х>Уе същият,като на У и Х mod У(остатъкът при дел на Х с У)
long gcd(long m, long n)
{ while ( n != 0)
{long rem = m % n;
m = n; n = rem; }
return m;}
Доказва се че след 2 итерации остатъкът е поне половината. => 2 logN = O(log(N))
Повдигане в степен
long pow(long x, int n)
{ if( n == 0) return 1;
if( n == 1) return x;// излишни
if (isEven(n))
return pow ( x*x, n/2);// брой умнож при
// нечетно <= 2 logN
else return pow( x*x, n/2) *x;}
може: return pow (x,n-1)*x; Тогава O(logN)
11. Конкретизация на анализа при рекурсия и множ.рекурсия. Матем извод
Анализът на алг.е ключът към пълноценно-то им разбиране,за да мд ги прилагаме ефе-ктивно към практ.зад.Той играе роля във всяка стъпка от процеса на конструиране и писане на алг. За да мд се извърши анализа точно е необх.да знаем някои базови правила: --при рекурсия:
А.long fact( int i)
{ if ( n <= 1) return 1;
else return n * fact(n – 1) ;
} получава се опашна рекурсия преминава в цикъл
O(N)
Б.long fib( int n)
{ if( n < = 1) return 1;
else
return fib( n – 1) + fib( n – 2);
}
тежък анализ, бавна
нека T(N) fib(n)
T( N ) = T( N- 1 ) + T( N–2 )+ 2
T( 0 ) = T(1) = 1
*ще докажем по индукция:
fib( N )< ( 5 / 3 )N
Fo, F1 = 1; F2 = 2; F3 = 3
съществува k Fk < (5/3)k
ще докажем : Fk+1< (5/3) k+1
док: Fк+1< (5/3)к +(5/3)к-1 < (3/5)(5/3)к+1+(3/5)2 *(5/3)к+1 <
((3/5) +(9/25))(5/3)к+1 < (24/25)(5/3)к+1 < (5/3)к+1
=> експоненциално – не е добре.
11.Рекурсия и дървета.Рекурсивни алг.
Рекурсията е фунд.понятие за информ. Тя е тясно свърз.с дърветата. Използваме дърве-та за да разберем рекурс.прог. Рекурсивен алг.е този,който при изпълн.си се обръща към себе си пряко или косвено поне 1 път. За да реализ.рекурс.алг. се използ.рекурс. ф-ии. Има 2 вида рекурсия:
- проста – в тялото си алг.се обръща поне 1 път към себе си пряко,но с др.аргументи, които постеп.намал.и се стига до кр.ст-сти, при които алг.не се обръща към себе си
- взаимна – алг.А1 се обръща на 1 или по-вече места към А2 и обратно. Мд има м/у повече от 2 алг.
Класич.пр.за рекурс.ф-я е факториел,която се декларира чрез рекурентната връзка
N!=N(N-1)! , N>=1 с 0!=1.Тя мд се представи със следния код:
Int factorial(int N)
{ if (N==0) return 1;
return N*factorial(N-1); }
Ф-ята връща коректна ст-ст,когато се вика с ст-сти на N,които са дост.малки,че N! да мд се представи като int. Тази ф-я е на прост цикъл for със същото предназн.
for ( t=1; i=1; i<=N; i++) t* = I;
Винаги е възможно да транформ.рекурс. прог.в нерекурс.,изпълн.същите изчисл. Използваме рекурсия,защото тя ни помага да изразим сложни алго-ритми в компактна форма. Например при използване на ф-ята факториел избягваме използ.на локални променливи. В др.случаи използ.на рекурс. води до създ.на неефективни алг.
Тези ф-ии трд удовл.=> главни свойства:
-да решават изрично основния случай
-всяко рекурсивно викане трд вкл. по-малка ст-ст на аргументите.
Дълбочина на рекурсията е степента на влагане на виканията по време на изчисл.В
общия сл.дълбочината ще зависи от входа. Когато реализ.реална рекурс.прог.трд взе-мем предвид, че средата за прог.трд поддъ-ржа стек с размер дълбочината на рекурс. За огромните зад.,необх.за този стек прост-ранство мд ни откаже от използ.на рекурс.
12.Подходът:разделяй и владей.Св-ва, известни алг.,реализ.,оценъчна формула
Идеята на този подход е обектът(входните данни)да се раздели на части и рекурсивно се намира реш.на всяка част и оттук за це-лия обект. Пр.намиране на макс.от N елем, съхранени в масив:а[0],a[1],…,a[N-1]
Нерекурс.реш:
for ( t = a[0]; i = 1; i < N; i++)
if ( a[i] > t ) t = a[i]
Рекурс.реш. се изр.в следното:поредицата от елем. a[l],…,a[r] се разделя на 2 пореди-ци: a[l],…,a[m] и a[m+1],…,a[r],намират се max елем.в двете части(рекурсивно) и се връща по-гол.от тях като max от редицата
Item max (Item a[ ], int l, int r)
{ Item u,v; int m = (l+r) / 2;
if (l == r) return a[l];
u = max (a, l, m);
v = max (a, m+1, r);
if (u > r) return u;
else return v; }
Използ.на метода се дължи на факта,че той дава по-бързи реш.отколкото тези,получе-ни с прости итеративни алг.
Св-во. Рекурс.ф-я,разделяща зад.с размер N на 2 незав,непразни части,които тя реша-ва рекурс.,се обръща към себе сиТази прог.извърш.конст,количество работа за всяко викане=>общото време е линейно.
Друг клас.пример е зад.за Ханойските кули
Дадени са 3 пръчки и N диска с дупки в ср. които мд се надяват на пръчките,дисковете са разл.по размер и първоначално са подре-дени на най-лявата от пръчките в ред най-големия диск(N)долу,най-малкия(1) горе. Зад.е да се преместят дисковете на следв. отдясно пръчка по => правила:
1)само 1 диск се премества в даден момент
2)в/у по-малък диск не мд се пост.по-голям
//Ние премест.кулата от дискове надясно чрез рекурсивно премест.наляво на всички с изкл.на най-долния,после премест.най-долния надясно,след което рекурсивно ме-стим кулата обратно в/у най-долния диск.
void hanoi ( int N, int d)
{ if ( N == 0) return;
hanoi ( N-1, -d);
shift (N, d);
hanoi ( N-1, -d); } //
Тази прог.дава рекурс.реш.на зад.Тя опр. кой диск трдб преместен при всяка стъпка и в коя посока (+ значи премести 1 пръчка надясно,прескачайки циклично към най-лявата,тръгвайки от най-дясната, а – значи 1 пръчка наляво,прескачайки циклично към най-дясната,тръгвайки от най-лявата)
Св-во. Рекурс.алг.разделяй и владей за зад. с Ханойските кули дават реш.с 2N – 1 мест.
За реш.на Ханойските кули имаме реш.ли-нейно по време според размера на изхода. За Ханойските кули обикн.разгл.реш.като екпоненц.спрямо времето,защото разглежд размера на зад.от гл.т.на броя на дисковете
13. Дървета. Основни понятия и класификации. Дефиниции и свойства.
Дървета.Осн.понятия и класифика-ции. Деф.и св-ва
Дърво е непразна съвкупност от върхове (възли)и ребра,които удовл.опр.изисква-ния.Върхът е прост обект,който мд има и да носи друга асоциирана инфо-,а реброто е връзкта м/у 2 върха. Път в дърво е списък от разл.върхове,в които последователни върхове са свързани с ребра в дървото.
Дефиниращо св-во за дърво е,че има само 1 път свърващ всеки 2 възела.Ако има >1 път м/у 2 възела,тогава имаме граф.
Дърво с корен–когато1възел е опр.за корен
Всеки възел,освен корена има точно 1 възел над себе си,родител,възлите директ-но под него се нар.негови деца.Възлите без деца,се нар.листа.
Наредено дърво-дърво с корен, в което е опр.реда на децата за всеки възел.
Ако всеки възел има опр.брой деца,явява-щи се в опр.ред,тогава имаме М-арно дър-во.Най-простият пр.е бинарното дърво.
Бинарното дърво се състои от 2 типа възли: външни,които нямат деца и вътрешни, кои-то имат точно 2 деца – ляво и дясно.
Деф.Бинарно дърво е или външен възел или вътр.възел,свързан към чифт бинар.дъ-рвета,които се нар.ляво и дясно поддърво.
Представянето,което използ.за реализ.на прог.използващи бинар.дървета е структу-ра с 2 връзки за вътрешни възли.Подобни са на свърз.списъци,но имат 2връзки на въ-
зел,вместо 1.
typedef struct node *link
struct node { Item item; link l, r; }
Връзките са указатели към възли,а всеки възел се съст.от елем.и чифт връзки.
Деф.1 М-арно дърво е или външен възел или вътр.възел,свързан с наред.последов. от М-арни дървета
Деф.Наредено дърво е възел,нар.корен,свъ-рзан към последов.от несвърз.дървета.
Разликата м/у наредено дърво и М-арно дърво е,че възлите в наредените дърв.мд имат всякакъв брой деца,а М-арно дърво трд има точно М деца.
Деф.Дърво с корен(ненаредено дърво) е възел,нар.корен,свърз.към мултим-во от дървета с корени.
Деф.Граф е м-во от възли и ребра,които свърз.двойки разл.възли. Последов.от реб-ра,водеща от 1 възел към друг,като никой възел не се среща 2 пъти,се нар.прост път.
Графът е свързан,ако същ.прост път свърз-ващ всяка двойка възли.Път,който е прост, с изкл.на 1-я и посл.възел,които са еднакви се нар.цикъл. Един граф е дърво,ако удовл. едно от => усл.
- има N-1 ребра и няма цикли
- има N-1 ребра и е свързан
- точно 1 път свързва всяка двойка върхове
- свързан е,но не остава такъв,ако махнем 1 от ребрата
14. Математически свойства на двоичните дървета.
Матем.св-ва на двоичните дървета
Св-во. Бинарно дърво с N вътр.възела има N+1 външни възела
Док.се по индукция.Бин.дърво без вътр.въ-зли има 1 външ.възел=>изпълн.за N=0.
За N>0,всяко бин.дърво с N вътр.възли има К вътр.възли в лявото си поддърво и N-K-1
вътр.възли в дясното си поддърво,за К м/у 0 и N-1,тъй като коренът е вътр.възел.Спо-ред индукц.хипотеза,лявото поддърво има К+1 външ.възли,а дясното->N-K=>сум.N+1
Св-во. Бинарно дърво с N вътр.възела има 2N връзки;N-1 връзки към вътр.възли и N+1 връзки към външ.възли..
Във вс.дърво с корен вс.възел освен корена има 1родител,а вс.ребро свързва възел с не-говия родител,така че има N-1 ребра,свърз. вътр.възли.Подобно вс.от N+1 външни възела има по 1 ребро към своя родител.
Деф.Нивото на възел в дърво е > от нивото на неговия родител.
Височина на дърво е max от нивата на въз.
Дължина на вътр.пътища в бинар.дърво е сума от нивата на вътр.му възли
Дължина на външ.пътища в бинар.дърво е сума от нивата на външ.му възли
Тези деф.са пряко свърз.с анализа на алг.
Св-во. Дълж.на външ.пътища в вс.бинар. дърво с N вътр.възела е с 2N по-гол. от дълж.на външ.пътища-Док.се по индукция
Св-во. Височ.на бинар.дърво с N вътр.въ-зела е >= от lgN и <= N-1
Док.Най-лошия сл.е дегенерирано дърво с 1листо,с N-1 връзки от корена до листото. Най-добрият сл.е балансирано дърво с 2 i
вътр.възли за всяко ниво i,освен за най-до-лното.Ако височ.е h,трд имаме:
2 h-1 < N+1 <= 2 h
Тъй като имаме N+1 външ.възела. Височ. в най-добрия сл.ще е = lgN
Св-во. Дълж.на вътр.пътища в бинар. дър-во с N вътр.въз.е>=Nlg(N/4) и <=N(N-1)/2
Бинар.дърв.се появяват мн.често в комп. прилож.и произв-стта е best при баланс.дър
15. Обхождане на дърво и граф.
Ще разгл.алг.за най-осн.обработваща дърв. ф-я:обхождане.При бин.дърв.имаме 2 връз-ки=>3 осн.последов.,по които да посет.въз.
- преред – посещ.възела,после лявото и дясното поддърво
- поред – посещ.лявото дърво,после възела и накрая дясното поддърво
- постред – посещ.лявото и дясното поддъ-рво и после възела
Тези 3 метода са за обхожд.в дълбочина.Те мд се реализ.чрез рекурс.прог:
void traverse (link h, void ( *visit)(link))
{ if h==NULL) return;
(*visit)(h);
traverse (h->l, visit);
traverse (h->r, visit); }
Тази рекурс.ф-я взема връзка към дърво ка-то арг.и вика ф-ята visit с арг.всеки от въз-лите на дървото.Ф-ята реализ.прередно об-хождане.Ако премест.викането на visit м/у рекурс.обръщ.,имаме поредно обхожд., а ако премест.след тях,имаме постред.обхож.
При използ.на нерекурс.,които използ.стек, правим опер.за вмъкване на дървото,които зав.от желаната последов.на обхожд:
- преред – вмък.в стека дясното поддърво после лявото и накрая възела
- поред – вмък.в стека дясното поддърво, после възела и накрая лявото поддърво
- постред – вмък.в стека възела,после дяс-ното поддърво и накрая лявото поддърво.
В стека не се вмък.нулевите връзки.
Друга стратегия за обхожд.е просто да по-сещаваме възлите отгоре надолу и отляво надясно – обхождане в широчина,защото вс.възли от дадено ниво се появяват заедно
void traverse (link h, void ( *visit)(link))
{ QUEUEinit(max); QUEUEput(h);
while ( !QUEUEempty())
{ (*visit)(h = QUEUEget());
if (h->l != NULL) QUEUEput (h->l);
if (h->r != NULL) QUEUEput (h->r);} }
При графите обхожд.се осъщ.рекурс. или се нар.още търсене в дълбочина.Това е прост рекурс.алг.Започв.от възел V,ние:
- посещаваме V;
- рекурс.посещ.вс.непосет.въз,достиж.от V
За да посетим вс.възли,свърз.към възел K в граф,ние го маркираме лкато посетен и то-гава рекурс.посещаваме вс.непосетени въз-ли от списъка на съседство на К.
void traverse (int k, void ( *visit)(int))
{ link t;
(*visit)(k); visited[k] = 1;
for ( t = adj[k]; t != NULL; t = t -> next)
if ( !visited[t->v]) traverse ( t ->v, visit); }
Разл.м/у търс.в дълбоч.и обобщ.обхожд.на дърво е,че е необх.да се предпазим изрич-но от посещ.на вече посетени възли.
Ако използ.опашка вместо стек,тогава има-ме търс.в широч.,което е аналогично на об-хождане в широч.на дърво.
Напр.за да посетим вс.възли,свърз.към въ-зел К в 1 граф,вмък.в К в опашка FIFO,по-сле влизаме в цикъл,където е следв.възел от опашката и ако не е посетен,го посеща-ваме и вмък.в опашката вс.непосетени въз-ли от списъка му на съседство.
void traverse (int k, void ( *visit)(link))
{link t;
QUEUEinit(V); QUEUEput(k);
while ( !QUEUEempty())
if (visited[k=QUEUEget()] == 0)
{(*visit)(k); visited[k] = 1;
for ( t = adj[k]; t != NULL; t = t -> next)
if (visited[t->v]==0) QUEUEput (t->v);} }
16. Рекурсивни алгоритми в двоични дървета.
.Рекурс.алг.в двоични дървета
Бин.дърв.мд се обхождат по няколко н-на:
- преред – посещ.възела,после лявото и дясното поддърво
- поред – посещ.лявото дърво,после възела и накрая дясното поддърво
- постред – посещ.лявото и дясното поддъ-рво и после възела
-както и в широчина
Често е необх.да намерим ст-стите на разл. структурни парам.за 1 дърво,само по даде-на връзка връзка към дървото.Следв.прог. съдържа рекурс.ф-ии за изчисл.броя на въ-злите и височината на дадено дърво.
int count (link h)
{ if ( h==NULL ) return 0;
return count (h->l) + count (h->r) + 1;}
int height ( link h )
{ int u,v;
if ( h == NULL ) return -1;
u = height ( h->l ); v = height ( h->r);
if ( u > v ) return u+1; else return v+1; }
Др.ф-я ни показва рекурс.алг.за обхождане на дърво е този за отпечатване на дърво. Ако отпеч.елемента преди рекурс.викане, получаваме прередно обхожд.Тази прог.до-пуска че елем.в възлите са символи:
void printnode ( char c, int h )
{ int i;
for ( i = 0; i < h; i++) printf (“ ”);
printf (“%c\n”, c); }
void show ( link x, int h )
{ if ( x==NULL) {printnode(‘*’,h); return; }
show (x -> r, h+1);
printnode (x -> item, h);
show (x ->l, h+1); }
17.Елементарни сортировки. Селект. сортировка. Сортиране чрез вмъкване
В много сортиращи прил. е възм. метода. к-то тр. да се избер. да е прост. алгорит. Поради сл. причини: 1 – во. Често сорт. прог. се изп. само веднъж и ако елем. сорт. не е по – бавна от др. части на прогр. не е нужно да се търси по – бърз метод. Ако бр. на сорт ел. не е мн. гол.(до няк. 100) също може да се избере пост метод. 2 – ро. Елементар. сорт са по удобни за малки фаилове. Бав. методи са добри също за почти сортирани фаилове. или такива които съдърж.голям бр.повтар. се ключове.