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)експоненти-ХАХВ=ХА+В ХА/ХВ=ХА-В ;
ХN +ХN =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)).
-
правило 2: ако T(N) е полином със степен k, то T(N) = O (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>
Сподели с приятели: