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

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

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

3. 
   Свързаност на обекти – алгоритъм с бързо обединение.Програмна реализация.Анализ и сравнение с алгоритъма за бързо намиране. Представяне в дърво.
   

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

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

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

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

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

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

Реализация:

{ 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. Mатематически основи в анализа на алгоритми. Използвани формули с експоненти, логаритми, редиц и.

Основните причини,за да извършваме матем.анализ на алг. са:
-за да сравним различни алг.за една и съща зад.
-за да предвиждаме производителността в нова среда
-за да задаваме ст-сти на параметрите на алг.
Алг.обикновено имат време за работа, пропорц. на една от следните ф-ии(N-главен параметър на нарастване):
1-инструкцията се изпълнява само веднъж или най-много няколко пъти, казваме че времето за работа на алг. е константа
log N-ако времето за работа на алг. е логаритмично,програмата става по-бавна с нарастването на N.Среща се при прог, които решават големи задачи.
N-времето е линейно,когато всеки вх. елемент се обработва по малко.Както се променя N,така се променя и вр. за работа
N logN-такова време за работа се по-лучава,когато алг.решават зад.,като я разделят на по-малки подзадачи,решават ги независимо и после обединяват решението
N²-когато времето е квадратично,алг.м д се използва практически само за малки зад. Появява се в алг,в които се обработват всички двойки от данни.
N³-ако алг.обработва тройка от данни,той има кубично вр.за работа,за малки задачи
2^N-вр.за работа нараства експоненциално, тези алг.намират малко прилож в практиката. Осн.формули,които се използ при работа с експоненти, логаритми и редици са: 1)експоненти-Х^АХ^В=Х^А+В Х^А/Х^В=Х^А-В ;
Х^N +Х^N =2(Х^N); 2^N +2^N =2^N+1

2. 
   логаритми- X^A=B, само ако log_x B=A
   

--T1: log_a B= log_cB/log_c A,при А,В,С>0,А!=1
--T2)logAB=logA+logB; за А,В>0
^x*2^y =AB=2^z ->X+Y=Z.

2. 
   
   i=0
   редици-Σ^N 2ⁱ=2^N+1-1;
   

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

i=1
-аритм.редици Σ^N I=(N(N+1))/2 ≈N²/2
и наистина 2+5+8+..(3к-1),което е 3(1+2+..+к)-(1+1+..+1),което е предст.и ка-то(к(3к+1))/2 => ((3к+1)к)/2=3(Х)-к =>

i=1
Х=(N(N+1))/2 ,което е ≈N²/2. Σ^N I²=(N(N+1)(2N+1))/6 ≈N³/3
Матем.озн,които се срещат във формулите, описващи поведението на алг са:

└^х ┘- закръгляне отдолу
┌_х┐-закръгляне отгоре lgN-двоичен логаритъм lnN-натурален логаритъм N!-функция факториел
F_N—числа на Фибоначи
0 1 1 2 3 5 8 13 21 34 55 ...
дефинирани по формулата
F_N=F_N-1+F_N-2 za N>=2,F₀=0,F₁=1
H_N—хармонични числа Н_N=1+1/2+1/3+...+1/N.

5. Въведение в рекурсията.Основни свойства на рекурсията.Типове рекурсии, аналлиз на производителността и доказателства.Формални техники за преобразуване на рекурсивни в нерекурсивни алгоритми;опашна рекурсия,множествена рекурсия.

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

Сподели с приятели: