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

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

┌_х┐-закръгляне отгоре lgN-двоичен лагаритъм lnN-натурален логаритъм N!-функция факториел

Дефиниции:

*T(N)=O(f(N)) ако съществуват с,n и за всяко N>=N₀ ->T(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.

цели:пренебрегване малки членове,облекчен анализ,оценка по горна граница. Пр.:N(N-1)/2->N²/2 или N=O(N) или 2а₀NH_N+a₁N+a₂->2а₀NH_N+O(N) (за големи N)

• 
  T(N)= Ω (g(N)) ако съществуват const c и n₀, такива че T(N) >+ cg(N) за N>n₀
  

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

1 – никакъв

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

lgN - лек

N² - с коефициент 4 N - удвоява

N³ - с коеф. 8

NlgN - малко > от двойно

пр: (N + O(1)) N + O(logN) + O(1)) = N + O(N) + O(Nlog(N)) + O(logN) + O(N) + O(1) = N² + O(NlogN) ≈ N² за големи 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(2N²) T(N)=O( N² )
правило 3 : log_к N = O(N) за всяко k ( логаритмите растат бавно)

5. Задача за намиране на максимум на подниз.решения.Анализ. 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)

цепим проблема на 2 части и т. н. рекурсивно. Съединяваме двете решения.
Max сума може да е на 3 места:
I пол.от числа II пол.от числа
for( int I = center; I > = left; I--)
{ leftBorderSum += a[I];
if(leftBorderSum > maxLeftBorderSum) maxLeftBorderSum = leftBorderSum }

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;
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. 
    Логаритми в анализа. Бинарно търсене, Евклидов алгоритъм за НОД, повдигане на степен. Анализ.
    

Един алг.е 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)

10. Рекурсия и дървета. Рекурсивни алгоритми

Рекурсията е фунд.понятие за информ. Тя е тясно свърз.с дърветата. Използваме дървета за да разберем рекурс.прог. Рекурсивен алг.е този,който при изпълн.си се обръща към себе си пряко или косвено поне 1 път. За да реализ.рекурс.алг. се използ.рекурс. ф-ии. Има 2 вида рекурсия: