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



страница1/5
Дата25.02.2018
Размер0.84 Mb.
  1   2   3   4   5
1.Осн.понятия.Варианти на алг.Влия-ние в/у произв-стта.Въведение в анализа

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

Инструкциите биват:

-безусловни-можем да преминем към следващата инструкция без условие

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

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



Свойства:

-Детерминантност - резултатите получени от дадена стъпка, трябва да се определят еднозначно от резултатите в предишните стъпки;при еднакви вх.данни за всяка стъпка трябва да има еднакви резултати.Ако това свойство се наруши-алгоритъмът става вероятностен(от краен брой стойности случайно се избира една).Всяка инструкция има код (КОП) и адрес,с които се указва.



-Крайност(финитност)-алг.и всяка негова стъпка се изпълняват за крайно време

-Дискретност- алг.във времето се изпълнява на интервали.В отделни моменти от интервала нямаме резултат.Това не е така при аналоговите устройства-при тях процесите протичат непрекъснато и м/у 2 момента мд имаме безкрайно много ст-сти,но точността е малка.Числата,с които работи ЦИМ се представят в краен интервал,в който мд представим краен брой стойности.



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

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



Видове:

1. според структурата:

неразклонени (линейни)- всички постъпили входни данни, се обработват по един и същ начин

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

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

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

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

3. според вероятността:

точни-изследват всички възможни случаи и дава оптимален резултат

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

2.Свързаност на обекти. Деф.на абстрак-тни опeрации в зад. Нач. алг.Алг. за БН. Прог.реализ.Представяне в дърво.

Дадена е послед.от цели числа, всяко число представлява някакъв обект. Записът p – q означава p e свързано с q. Връзката е тран-зитивна,т.е ако p - q и q – r, то p - r. Иска се да премахнем ненужните двойки от множ., т.е.когато в прог.се въведе двойка p – q, тя трд я изведе само ако според досега въве-дените двойки p не е свърз. с q. Зад.ни е да се направи прог.която помни дост. инф. за постъпилите двoйки до момента и може да прецени дали има нова връзка м/у обекти.В зад.се иска да знае дали опр.двойка е свър-зана,а не да покаже 1 или всички пътища, които я свързват.Намира важни прил.напр. връзки в компютърна,ел.мрежа и др.______

От теорията на графите => N обекта са свързани ,когато има точно N – 1 изведени двойки в алг.на свързаност.

Св-во. Алг.с бързо намиране изпълнява поне MN инструкции,за да реши зад за свърз с N обекта,която вкл. M обединения

Абстрактни операции, необх. за алг. -

Намиране и Обединение

След като прочетем нова двойка p – q от входа,изпълн.опер.намиране за всеки член на двойката. Ако те са в едно множество, минаваме на следв.двойка. Ако не са, пра-вим опер.обединение и извежд. двойката



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

Алгоритъм за бързо намиране(БН)

P q 0 1 2 3 4 5 6 7 8 9

3 4 0 1 2 4 4 5 6 7 8 9

4 9 0 1 2 9 9 5 6 7 8 9

8 0 0 1 2 9 9 5 6 7 0 9

2 3 0 1 9 9 9 5 6 7 0 9

5 6 0 1 9 9 9 6 6 7 0 9

2 9 0 1 9 9 9 6 6 7 0 9

5 9 0 1 9 9 9 9 9 7 0 9

7 3 0 1 9 9 9 9 9 9 0 9

4 8 0 1 0 0 0 0 0 0 0 0

0 2 0 1 0 0 0 0 0 0 0 0

5 6 0 1 0 0 0 0 0 0 0 0

6 1 1 1 1 1 1 1 1 1 1 1

Осн. на този алг е масив с цели числа с св- вото,че p и q са свърз ,когато p и q ел. в масива са ≡.За да изпълним обедин p и q минаваме през масива като променяме вси-чки клетки с същата ст-ст като p да имат същата ст-ст като q.



Програмна реализация

#include

#define N 10 000

main ()

{ int I, p, q , t, id[N];

for( I = 0; I < N; I++) id[I] = I;

while(scanf(“%d, %d \n”, &p,&q) == край

{

if( id[p] == id[ q ] )continue;

for( t = id[p], I = 0; I

if(id[I] == t) id[I] = id[q];

printf(“нова връзка”)

}}

Представ. в дърво.



Част II за дървото:



3. Свързаност на обекти – алг. за бързо обединение(БО).Прог.реализ. Анализ и сравн. с алг. за БН. Предст.в дърво

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



Програмна реализ. за всяко p и q:

for ( I = p; I != id[I]; I = id[ I ]);

for ( j = q; j != id[ j ]; j = id [ j ]);

if( I == j ) continue; // двата указат. са //еднакви => свързани числа

id[I ] = j; // обединяваме

printf( “ %d %d \n”, p, q);

При обработване двойката p - q ние:

1.следваме указатели от p докато id[I]= = I

2.следваме указатели от q докато id[j]= = j.

3.ако I!= j => id[I] = id[j] => обединението е просто прилепяне към дърво

Анализ и сравнение

Алг.за БО е по бърз от този за БН,защото той не трд минава през целия масив за вся-ка входна двойка. Изпълн.на алг.за БО за-виси в гол.степен от х-ра на входа.Разлика-та м/у бързо обед. и намир. представлява подобрение, но недостатъка е че не може да се гарантира че подобрението в бързи-ната е значително защото вх. данни може да са такива че да направят намир. бавно.



Св-во. За M>N,алг.с БО мд отнеме повече от MN/2 инструкции, за да реши зад. за свързаност с M дв.от N обекта.

Док-во.Ако на вх. двойките идват подреде-ни така: 1-2, 2-3 и т.н След N-1 подобни дв. имаме N обекта в 1 и също множ,а дървото което се получило е права линия. Като N сочи към N -1, N – 1 сочи към N – 2 и т.н. За да изпълни опер.намиране за обекта N прог.трд мине през N-1 указателя. Ср. брой указатели е (N-1) /2. Ако останлите двойки свързват N с някакъв друг обект,опер.на-миране за всяка от тези дв. вкл. поне N – 1 указателя. Общата сума за М-те опер нами-ране за тази последов.от вх. дв е > МN/2

Представ в дърво.



Част II за дървото:



4. Свързаност на обекти–алг.с претегле-но бързо обединение(ПБО).Реализация. Анализ. Представяне в дърво.

За избягване на лоши сл. при алг. за БО е създаден алг.за ПБО. Вместо случайно да се свързва II дърво към I при опер.oбедине-ние,се следят броя на върховете в всяко дърво и винаги свързваме по-малкото дър-. во към по-голямото Промяната изисква ма- лко повече код и още 1 масив, в който се държат броя на върховете, но ефективност-та съществено се подобрява.



Св-во. Алг. проследява най-много 2 lgN указателя за да определи дали 2 измежду N обекта са свързани.

Док-во:за k обекта имаме max lg k указате-ля. След обединение на множ.oт I върха с множ.oт J върха,увелич.броя на указатели-те,които трд се проследят в по-мал.множ. с 1,но сега те са в множ.с размер I+J,така че св-вото е запазено, защото:1+lgI=lg(I+I)<= <=lg(I+J).След N обединения, в най-тежък случай - 2 lg N за всички M двойки - max MlgN инстукции.Много по-добро от МN/2.

За големи числа -почти линеен алг.

 възможни подобрения:

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

2. всяко ребро се разглежда 1 път - не е нужно да се помни => спестяване на памет.

Реализация:

#include

#define N 10 000

main()

{ int I, j, p, q, id[N], sz[N];

for(I=0;I

{id[I] = I; sz[ I] = 1;}

while(scanf(“%d %d\n”,&p,&q) == край)

{for( I = p; I != id[ I ]; I = id[ I ]);

for( j = q; j != id[j ]; j = id[ j ]);

  if (I == j ) continue;



if( sz [ I ] < sz [ j ])

{ id[ I ] = j; sz[ j ] += sz[ I ];}

else { id[ j ] = I; sz [ I ] += sz[ j ];}

printf ( % d %d \n”, p, q);}}

Представ в дърво:



част II на дървото.





5.Матем.основи в анализа на алг. Използвани формули с експоненти, логаритми, редици.Доказателства

Основните причини,за да извършваме матем.анализ на алг. са:

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

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

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

Алг.обикновено имат време за работа, пропорц. на една от следните ф-ии(N-главен параметър на нарастване):

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

log N-ако времето за работа на алг. е логаритмично,програмата става по-бавна с нарастването на N.Среща се при прог, които решават големи задачи.

N-времето е линейно,когато всеки вх еле-мент се обработва по малко.Както се про-меня N,така се променя и вр. за работа

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

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

N3-ако алг.обработва тройка от данни,той има кубично вр.за работа,за малки задачи

2N-вр.за работа нараства експоненциално, тези алг.намират малко прилож в п-ката.

Осн.формули,които се използ при работа с експоненти, логаритми и редици са:

1)експоненти-ХАХВА+В ХАВА-В ;

ХNN =2(ХN); 2N +2N =2N+1

2)логаритми- XA=B, само ако logx B=A

--T1: loga B= logcB/logc A,при А,В,С>0,А!=1

док: нека Х=logc B; Y=logc A; Z=loga B; тъй като Сх = В,Сy =A, Az =B,то комбинираме: B=Cx = Az =(Cy)z -> X=Y*Z

--T2)logAB=logA+logB; за А,В>0

док:нека X=logA; Y=logB,Z=log AB; за база 2->2x =A,2y =B, 2z=AB->

2x*2y =AB=2z ->X+Y=Z.

3)редици-ΣNi=0 2i=2N+1-1;

ΣNi=0AI=(AN+1-1)/(A-1) при 0<А<1 то ΣNi=0AI<=1/(1-A); при N->безкр.,сумата клони към 1/(1-А)

Док: нека S=1+A+A2+..;тогава АS=A+A2+A3+…;то S-AS=1 и следователно S=1/(1-A)

-аритм.редици ΣNi=1I=(N(N+1))/2 ≈N2/2

и наистина 2+5+8+..(3к-1),което е 3(1+2+..+к)-(1+1+..+1),което е предст.и ка-то(к(3к+1))/2 => ((3к+1)к)/2=3(Х)-к =>

Х=(N(N+1))/2 ,което е ≈N2/2.

ΣNi=1I2=(N(N+1)(2N+1))/6 ≈N3/3

док: вярно за N=1=>вярно и за 1<=к<=N.Правим проверка за N+1:

ΣN+1i=1I2 = ΣNi=1I2+(N+1)2=

(N(N+1).(2N+1))/6+(N+1)2=

(N+1)*[(N(2N+1)/6)+(N+1)]=(N+1)*[(2N2+7N+6)/6]=[(N+1)(N+2)(2N+3)]/6.

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

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

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

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.

6.Въведение в рекурсията. Осн.св-ва на рекурсията.Типове рекурсии,анализ на производителността и доказателства

Рекурсивен алг.е този,който при изпълн.си се обръща към себе си пряко или косвено поне 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); }

Рекурс.ф-ии мд дадат сигурност,компакт реализ.Тези ф-ии трд удовл.=>глав. св-ва:

-да реш.изрично осн.сл.(усл.за край)

-всяко рекурс.викане трд вкл.по-малка стойност на аргументите. Пример:

int F (int i)

{ if (i<1) return 0;

if (i==1) return 1;

return F(i-1) + F(i-2)

Рекурс.реализ.на тази зад.е изкл.неефекти-вна.Алг.е с експоненц.време(изкл.мн.повт)

Типове рекурсия и оценки:

А) премахва 1 елемент от N входящи числа при циклично прохождане Cn=Cn-1+N; C1=1



Док: Cn=Cn+1+N=Cn-2+(N-1)+N=

C1.. +2+..N=1+2+…+(N-2)+(N-1)+N=

=[N(N+1)]/2.=>Cn≈N2/2

Б)рекурсии с разполовяване на входния поток на всяка стъпка

Cn=2Cn/2+1 ; C1=1;

Док:некаN=2n(пр.битове за предст.на N)=>

C2n=C2n-1+1= C2n-2+1+1= C2n-3+3=

…=C20+n=n+1 =>

оценката на CN зависи от броя битове, необходими за представяне на N-> lgN

В)рекурсивни програми,разполовяващи входа,но преглеждащи всеки елемент

Cn=Cn/2+N; C1=0 ;



Док: разписва се като N+N/2+N/4+N/8+… =>Оценката е строго пропорц.на вх.->2N

Г)рекурсии с лин.обхождане на входа преди,по време или след разполов.на входа

Cn=2Cn/2+N;C1=0(алг.“разделяй и владей”)

Док: C2n=2C2n-1+2n ; делим на2

->: C2n/2n=[C2n-1/2n-1]+1=[2C2n-2+2n-1]/2n-1+1 =C2n-2/2n-2+2=…=n ->CN=NlgN



7. Опасности при рекурс.алг. Формални техники за преобразуване на рекурс. в нерекурс.алг:опашнарекурсия,множест-вена рекурсия, рекурсия в средата, алг.решения с взаимна рекурсия

Рекурсивен алгоритъм е този, който решава проблем чрез решаването на един или по-малки екземпляри на същия проблем.За да реализираме рекурсивни алг, използваме рекурсивни функции-рекурсивна функция е тази,която вика себе си.Рекурентни връзки са рекурсивно дефинирани функции. Една рекурентна връзка дефинира функция,чиято деф. област е неотрицателните цели числа или чрез някакви начални стойнос-ти,или (рекурентно) от гледна точка на нейни собствени стойно-ти върху по-малки цели числа.Може би най-известната та-кава функция е функцията факториел,която се декларира чрез рекурентната връзка N!=N(N-1)! , за N>=1, 0!=1.

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

Int f(int x)

{ if (x==0) return 0;

else return (2*f(x-1)+x*x);

} т.е. f(0)=0; f(x)=2f(x-1)+x2 ;

За да използваме рекурсия ние трябва да се съобразяваме с някои правила,напр. За предпочитане е реализация с 1 for(ако е възможно), и никога в 1 стъпка повече от 1 рекурсия,защото тогава възниква опасност от т.нар. множествена рекурсия(като при числата на Фибоначи),f(N)=f(N-1)f(N-2);

пр: voidDoubleCountDown (int N)

{ if(N<=0);

{DoubleCountDown(N-1);

DoubleCountDown(N-1)}

/*времето се удвоява ???

нека имаме означението Т(N) и Т(0)=1; времето на изпълнение се подчинява на формулата:1+2Т(N-1)



N 0 1 2 3 4 10

T(N) 1 3 7 15 31 2047

виждаме Т(N) = 2N+1 – 1->O(2N)

Може също да се получи и индиректна рекурсия:пр. Криви на Шерпшински О(4N). При това се получава разход на памет:

Int BadForMemory()

{ int *x;

GetMemory(x,10 000);

BadForMemory(); }

Съществуват техники на формално преобразуване на рекурс в нерекурс алг.

1)Премахване на опашна рекурсия

procedure Recurse(A: Integer);

begin

//извършва нещо



Recurse(B)

end;


procedure NonRecurse(A: Integer)

begin


while(not done) do

begin


//извършва нещо

A:=B;


end;

end ;


2)Запаметяване на междинни резултати :

пр.: Fibonacci числа: за Fib(29)-> Fib(1) и Fib(0) се изчисляват 832 040 пъти??? Междинните резултати се съхраняват в таблица след първото изчисляване.

3)Подменяне посоката top-down към botton-up(пр. с Fibonacci числа)

При тази техника оценката за алг.на Fibonacci е О(N) за Fib(N) вместо O(Fib(N))

Напр. за Pentium 166 MHz и Fib(40)----155 sec с рекурсивен алгоритъм,докато с тази модификация Fib(1476) се смята за

4)Подмяна на алг.чрез преструктуриране на кода:оформяне proc. за съхраняване на информацията,стъпка и възстановяване:

пр.:procedure Recurse(num:Integer);

begin


Recurse(
)



end ;


преструктурираме:

procedure Recurse(num:Integer);

begin

Recurse(
)



end ;


и procedure Recurse(num:Integer);

var pc:Integer;

begin

pc:=1;


repeat

case pc of

begin

if(базов случай) then pc:=2 //прескачаме еркурсията

else begin //съхраняваме пром. за следрекурсивното викане и рс=2;устано-вяваме пром. нужни при рекурсия (напр. n:=n-1) и преход към начало на рекурсията:

pc:=1; end ; end;

begin

pc:=0; end;

//код след рекурсията

5)алг.промяна при сложни случаи на взаимна рекурсия:пр. криви на Шерпински:

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

SierpA,SierpB,SierpC and SierpD.

Всяка от тях вика останалите,които от своя страна я викат рекурсивно.Всяка служи за изчертаване на горна,лява,долна и дясна част от общата картина .При рекурсивен вариант на всяка процедура оценкатана алгоритмичната сложност е О(4N).

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



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

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

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

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

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

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

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

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

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)).



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

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

10. Конкретизация на правилата за анализ на алг в: цикли 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)



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

=> експоненциално – не е добре.



12. 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); }
  1   2   3   4   5


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

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