ALG2

72

Rozdział 3. Analiza sprawności algorytmów

n o) = i,

i = A + O,

A =    1.

Po tych karkołomnych wyliczeniach otrzymujemy: T(n)=n+J.

Jest to jest to identyczne z poprzednim rozwiązaniem¹.

Metoda równań charakterystycznych jest jak widać bardzo elastyczna. Pozwala ona na szybkie określenie złożoności algorytmicznej nawet dość rozbudowanych programów. Są oczywiście zadania wymagające interwencji matematyka, ale zdarzają się one rzadko i dotyczą zazwyczaj programów rekurencyjnych o nikłym znaczeniu praktycznym.

3.7.3.Rozkład „logarytmiczny”

Z rozdziału poprzedniego pamiętamy zapewne zadanie poświęcone przeszukiwaniu binarnemu. Jedną z możliwych wersji funkcji² wykonującej to zadanie jest:

int binary_search(int ^łtab,int x, int lcft,int right)

(

if(left==right) if (t[left]==x)

return left;

else    //    element    znaleziony

return -1;    //    element    nie odnaleziony

else

f

int mid-(left+right)/2; if(tab[mid|==xj

return mid;    //    element    znaleziony!

else

if(x<tab[mid])

return szukaj rec(tab,x,left,mid); else

return szuka j_ree (tab, x,inid, right) ;

}

Jaka jest złożoność obliczeniowa tej funkcji? Analiza ilości instrukcji porównali prowadzi nas do następujących równości:

1

   Jeśli dwie metody prowadzą do takiego samego, prawidłowego wyniku, to istnieje duże prawdopodobieństwo, iż obie są dobre...

2

   Innej niż poprzednio zaproponowana.