1. Основни понятия. Варианти на алгоритми. Влияние върху производителността. Въведение в анализа Алгоритъм


Анализ на алгоритми. Математически обозначения, дефиниции и правила в анализа



страница2/5
Дата31.12.2017
Размер0.81 Mb.
#38451
1   2   3   4   5

8. Анализ на алгоритми. Математически обозначения, дефиниции и правила в анализа.

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

Анализ на алгоритми.Матем. обозначения и деф. в анализа. Базови правила в анализа на алг.

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

-за да сравн разл.алг. за една и съща задача

-за да предвижд.произв-стта в нова среда

-за да задаваме ст-сти на парам на алг

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

х ┘- закръгляне отдолу

х┐-закръгляне отгоре

lgN-двоичен лагаритъм

lnN-натурален логаритъм

N!-функция факториел

FN—числа на Фибоначи

0 1 1 2 3 5 8 13 21 34 55 ...

дефинирани по формулата

FN=FN-1+FN-2 za N>=2,F0=0,F1=1

HN—хармонични числа

НN=1+1/2+1/3+...+1/N.

Дефиниции:

*T(N)=O(f(N)) ако съществуват с,n и за всяко N>=N0 ->T(N)

цели:пренебрегване малки члено-ве,облекчен анализ,оценка по горна граница. Пр.:N(N-1)/2->N2/2 или N=O(N) или 2а0NHN+a1N+a2->2а0NHN+O(N)

(за големи N)


  • T(N)= Ω (g(N)) ако съществуват const c и n0, такива че T(N) >+ cg(N) за N>n0
    *T(N) = O (h(N) ) ако и само ако T(N) = O(h(N)) и T(N) = Ω(h(N)) казваме :

“grouth rate” на T(N) = “grouth rate “ h(N)
ефект от удвояване на голем.на зад в/у t:
1 – никакъв

2N- квадратичен


lgN - лек

N2 - с коефициент 4


N - удвоява

N3 - с коеф. 8


NlgN - малко > от двойно
пр: (N + O(1)) N + O(logN) + O(1)) = N + O(N) + O(Nlog(N)) + O(logN) + O(N) + O(1) = N2 + O(NlogN) ≈ N2 за големи N.

Базовите правила в анализа на алг. са:



  • правило 1: ако T1(N) = O(f(N)) и T2(N) = O(g(N)), то

а)T1(N) + T2(N) = max (O(f(N)), O(g(N)).

b)T1(N)*T2(N)= O(f(N) * g(N)).



  • правило 2: ако T(N) е полином със степен k, то T(N) = O (N к )

напр: вместо T(N) =O(2N2)  T(N)=O( N2 )

  • правило 3 : logк N = O(N) за всяко k ( логаритмите растат бавно)

Конкретизация на правилата за анализ на алг в: цикли for, вложени цикли, последов.блокове, оператор if.

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



  • for (i= 1; i < n; i++)

  • for (j = 0; j < m ; j++) k++;

  • O(N 2).

-при последователни оператори важи правилото за максималното,а именно: ако T1(N) = O(f(N)) и T2(N) =О(g(N)), то T1(N) +T2(N)= max (O(f(N)), О(g(N)).

Пр.:for ( I = 0; … ) a[I] = 0;оценката е О(N);

а ако имаме for ( I = 0; ……………)

for( j =к; ………….)

оценката е O(N^2 )

a[I] = a[j] + I;

--при оператор if напр.:


  • if( ) S1 else S2

  • t <= t test + max( tS1, tS2)


9. задача за намиране максимум на подниз. решения. Анализ.

. 4варианта за реш.на зад.за максимум на подниз.Алг.и програмно реш.Матем. извод,определящ производителността

1. преглед на всички възможности
int maxSubSum1(const vector &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 – ро. Елементар. сорт са по удобни за малки фаилове. Бав. методи са добри също за почти сортирани фаилове. или такива които съдърж.голям бр.повтар. се ключове.





Сподели с приятели:
1   2   3   4   5




©obuch.info 2024
отнасят до администрацията

    Начална страница