Algorytmy i struktury danych
wykład 5
Analiza sprawności
algorytmów
1
Kryteria oceny programu
sposób komunikacji z użytkownikiem
(interfejs)  ważny z punktu widzenia
użytkownika
szybkość i sprawność wykonania założonych
swoich podstawowych funkcji  ważne z
punktu widzenia użytkownika oraz
programisty
2/45
Złożoność obliczeniowa
algorytmów
wynika często ze stopnia skomplikowania
problemu, którego rozwiązanie umożliwia
algorytm/program
można ją określić porównując efektywność
wykonania zadania przy różnych sposobach
rozwiązania go (czas, zużycie zasobów)
można ją określić również za pomocą aparatu
matematycznego
3/45
Podział programów ze względu
na ich złożoność
prosty algorytm
najczęściej krótki, czytelny kod
małe zapotrzebowanie na pamięć
mała złożoność obliczeniowa
trudny algorytm
najczęściej długi, skomplikowany kod
duża złożoność obliczeniowa
duże zapotrzebowanie na zasoby systemowe
4/45
Główny cel analizy złożoności
algorytmów
wybór rozwiązania, które zrobi
to samo ale szybciej
potrzebuje mniej nie wymaga tak dużej
pamięci mocy obliczeniowej
złożoność pamięciowa złożoność czasowa
5/45
Czy czas wykonania algorytmu
może stanowić o jego złożoności?
tak pod warunkiem zapewnienia identycznych
warunków wykonania algorytmu
jeżeli nie, to należy wziąć pod uwagę:
rodzaj komputera, częstotliwość taktowania, procesor
oraz wielkość pamięci
czy program był wykonywany jako jedyny i
ewentualnie jaki miał priorytet
system operacyjny
język programowania, rodzaj kompilatora, ustawienia
optymalizacji kodu
6/45
Parametr wpływający na czas
wykonania zadania
rozmiar danych
funkcja przeszukująca listę jest uzależniona od jej
długości
dla funkcji sortującej tablicę istotny jest rozmiar
tablicy oraz typ danych jej elementów
dla funkcji rekurencyjnej ważna jest wielkość danej
wejściowej
7/45
Analiza przypadków
wykonania algorytmu
najgorszy (pesymistyczny) rodzaj/zakres
danych wejściowych, dla których czas wykonania
algorytmu jest najdłuższy lub dłuższy niż zwykle
średni (oczekiwany) zwykły czas realizacji
algorytmu, dla najczęściej przetwarzanych danych
lub danych losowych, czas oczekiwany w
przeważającej części przypadków
najlepszy (optymistyczny) rodzaj/zakres
danych wejściowych, dla których czas wykonania
algorytmu jest najkrótszy lub krótszy niż zwykle
8/45
Typy złożoności algorytmów
złożoność praktyczna (T) jeżeli znamy czas tc
operacji elementarnych oraz liczbę n operacji,
możemy oszacować czas T(n) potrzebny do
wykonania algorytmu
złożoność teoretyczna (klasa algorytmu)
określenie, jaki typ funkcji matematycznej
występującej w określeniu złożoności praktycznej,
odgrywa dominującą rolę i wpływa najsilniej na czas
wykonania algorytmu
9/45
Notacja asymptotyczna
zakłada się nieograniczony rozmiar danych na
których pracuje algorytm
założenie nieograniczonego rozmiaru danych
pozwala na:
pominięcie stałych współczynników
pominięcie nieistotnych składników funkcji i skupienie
uwagi na składniku najistotniejszym, rosnącym
najszybciej
asymptotyczna złożoność algorytmu rząd
wielkości czasu działania algorytmu dla dużych
danych
10/45
Notacje złożoności teoretycznej
O asymptotyczne ograniczenie od góry
(najgorszy przypadek, pesymistyczny)
Ś asymptotyczne ograniczenie od dołu i od
góry (asymptotyczne oszacowanie dokładne)
� asymptotyczne ograniczenie od dołu
(najlepszy przypadek)
11/45
Notacja typu O
O(g(n)) =� { f :T : N a� R
($�c �� R+� )($�n0 �� N)("�n ł� n0)�� f (n)Ł�c �� g(n)}
f(n)=O(g(n)) -> g(n) jest
c"g(n)
asymptotycznym
oszacowaniem górnym dla
f(n)
f(n)
dla funkcji g(n) O(g(n))
oznacza zbiór funkcji
dla n>no f(n) nie przekracza
g(n)
n0 n
12/45
Notacja typu �
W�(g(n)) =� { f :T : N a� R
($�c �� R+� )($�n0 �� N)("�n ł� n0)�� f (n)ł� c �� g(n)}
f(n)
f(n)=�(g(n)) -> g(n) jest
asymptotyczną granicą
c"g(n)
dolną f(n)
n0 n
13/45
Notacja typu Ś
Q�(g(n)) =� { f :T : N a� R ($�c1,c2�� R+� )($�n0 �� N) ��
c1�� g(n) Ł� f (n) Ł�c2�� g(n)}
c2"g(n)
f(n)
f(n)=Ś(g(n)) -> g(n) jest
asymptotycznie dokładnym
c1"g(n)
oszacowaniem f(n)
n0 n
14/45
Przykłady klas złożoności
obliczeniowych
1 stała
n liniowa
log(n) logarytmiczna
n"log(n) liniowo  logarytmiczna
n2 kwadratowa
nc wielomianowa
cn wykładnicza
n! wykładnicza (n!>2n dla ne"4)
15/45
Tempo narastania wartości
funkcji
300
250
200
150
100
50
0
0 10 20 30 40 50
n n2 nlogn
16/45
Przykładowe czasy wykonania
algorytmów różnych klas
Założenia:
czas wykonania jednej operacji elementarnej
wynosi 1 mikrosekundę
czas wykonania algorytmu jest proporcjonalny
do odpowiadającej operacji matematycznej,
np.: dla funkcji n2 i danej wejściowej x czas
jest proporcjonalny do x2
17/45
Przykładowe czasy wykonania
algorytmów różnych klas -zestawienie
L. elem.
10 20 30 40 50 60
klasa
0.000001 s 0.000001 s 0.000001 s 0.000002 s 0.000002 s 0.000002 s
log(n)
0.00001 s 0.00002 s 0.00003 s 0.00004 s 0.00005 s 0.00006 s
n
0.00001 s 0.000026 s 0.000044 s 0.000065 s 0.000085 s 0.000107 s
n"log(n)
0.0001 s 0.0004 s 0.0009 s 0.0016 s 0.0025 s 0.0036 s
n2
0.001 s 0.008 s 0.027 s 0.064 s 0.125 s 0.216 s
n3
0.001 s 1.0 s 17.9 min 12.7 dni 35.7 lat 366 w
2n
0.59 s 58 min 6.5 lat 3855 w 200"106 w 1.3"1013 w
3n
3.6 s 768 w 8.4"1016 w 2.6"1032 w 9.6"1048 w 2.6"1066 w
n!
18/45
Klasy poznanych algorytmów
sortowania
wstawianie między �(n) i O(n2)
wybieranie O(n2)
bąbelkowe O(n2)
wstrząsanie O(n2)
szybkie O(nlog(n)) / O(n2)
scalanie O(nlog(n))
kopcowanie O(nlog(n))
19/45
Własności funkcji O(f(n))
c"O(f(n) = O(f(n))
O(f(n))+O(f(n)) = O(f(n))
O(O(f(n))) = O(f(n))
O(f(n)) " O(g(n)) = O(f(n) " g(n))
O(f(n) " g(n)) = f(n) " O(g(n))
20/45
Złożoność teoretyczna (klasa
algorytmu) - przykłady
T(n) O
2n+1 O(n)
n2+n+1 O(n2)
3n+n2+n O(3n)
21/45
Złożoność teoretyczna (klasa
algorytmu)  przykłady
Złożoność praktyczna T(n)= 4n2+2n+3
Szacowanie
4n2+2n+3 d" 4n2+2n2+3n2 =9n2 O(n2 )
Złożoność praktyczna T(n)=n3+n2+2n+1
Szacowanie
n3+n2+2n+1 d" n3+n3+2n3+n3 =5n3 O(n3 )
22/45
Typy złożoności obliczeniowej
Przykład przeszukiwanie kolejnych
elementów n-elementowej tablicy tab[i] w
celu odnalezienia zakładanej wartości x
przypadek najkorzystniejszy x=tab[1],
T(n)=1
przypadek najgorszy x=tab[n], T(n)=n
przypadek średni x=tab[i], 1 < i < n,
T(n)=(1-p)"n+(n+1)"p/2
p - prawdopodobieństwo, że x jest w tablicy, wszystkie możliwe
położenia jednakowo prawdopodobne
23/45
Analiza złożoności algorytmu
wyszukiwania elementu w tablicy
void szukaj(int tab[], int w) {
{
int i,j,wtemp;
tc, n razy
while(tab[i]!=w)
i=i+1;
ta, n-1 razy
cout<< pozycja= <}
T(n) = n"tc+(n-1)"ta = n"tc+ n"ta-ta =
= n"(tc+ta)-ta => O(n)
ta  czas operacji przypisania, tc  czas operacji porównania, n - liczba elementów
24/45
Analiza złożoności sortowania
 przez wstawianie
void sort_wstaw(int t[],int n) dla n-1 elem.
dla n-1 inkr. +
+ ostatnie spr.
pierwsza inicjal.
{
int j,wtemp;
tc, n razy ta, n razy
for(int i=1;i{
2"ta, n-1 razy
j=i; wtemp=t[j];
n-�1
2 ��tc, n -� 1+� j
while(t[j-1]>wtemp && j>0) ��
j=�1
{
n-�1
t[j]=t[j-1];
2 ��ta, j
dla każdego j max. j
��
j--;
j=�1 por. + kończące pętlę
}
t[j]=wtemp;
ta, n-1 razy
max. 1 raz dla 2.elem.,
}
max. n-1 razy dla ost.
}
zmienna liczba powtórzeń
stała liczba powtórzeń
25/45
Szacowanie złożoności (1)
n-�1 n-�1
T (n) =� tc �� n +� ta �� n +� (2��ta)��(n -� 1) +� ta ��(n -� 1) +� 2 ��tc ��(n -�1+� j) +� 2 ��ta �� j
�� ��
j=�1 j=�1
T (n) =� n ��(tc +� 4 ��ta) -� 3��ta +� 2��tc �� n -� 2 ��tc +�
+� (1+� 2 +� 3 +� ...+� n -�1)��(2 ��tc) +� (1+� 2 +� 3 +�...+� n -� 1) ��(2��ta)
przypadek pesymistyczny, tablica
przypadek optymistyczny,
posortowana odwrotnie
tablica posortowana zgodnie
T (n) =� n ��(tc +� 4 ��ta) -� 3��ta +� (n -� 1)��(2 ��tc) +� 0 ��(2 ��ta)
brak zamian
każdy element
elementów
porównywany tylko 1 raz 26/45
Szacowanie złożoności w notacji
typu O (cz. 1)
T (n) =� n �� (3 �� tc +� 4 �� ta) -� 3 �� ta -� 2 �� tc +�
n �� (n -� 1) n �� (n -� 1)
+� ( ) �� (2 �� tc) +� ( ) �� (2 �� ta )
2 2
T (n) =� n ��(3��tc +� 4 ��ta) -� 3��ta -� 2 ��tc +� (n2 -� n)��tc +� (n2 -� n)��ta
T (n) =� n ��(3��tc +� 4 ��ta) -� 3��ta -� 2 ��tc +� n2 ��tc -� n ��tc +� n2 ��ta -� n ��ta
T (n) =� n2 ��(tc +� ta) +� n ��(3��tc +� 4 ��ta -� tc -� ta) -� 3��ta -� 2 ��tc
T (n) =� n2 ��(tc +� ta) +� n ��(2 ��tc +� 3��ta) -� 3��ta -� 2 ��tc
27/45
Szacowanie złożoności w notacji
typu O (cz. 2)
T (n) =� n2 ��(tc +� ta) +� n��(2��tc +� 3��ta) -� (3��ta +� 2��tc)
tc +� ta =� c1, 2��tc +� 3��ta =� c2,
T (n) =� n2 ��c1+� n��c2 -� c2 =� n2 ��c1+� (n -�1)��c2
T (n) =� n2 ��c1+� (n -� 1)��c2 Ł� n2 ��c1+� n ��c2 Ł�
Ł� n2 ��c1+� n2 ��c2 =� (c1+� c2)�� n2 ��
�� O(T (n)) =� O(n2 )
28/45
Szacowanie złożoności w notacji
typu �
T (n) =� n��(tc +� 4 ��ta) -� 3��ta +� (n -� 1) ��(2 ��tc) +� 0 ��(2��ta)
T (n) =� n��(tc +� 4 ��ta) -� 3��ta +� n ��(2��tc) -� 2��tc
T (n) =� n��(3��tc +� 4 ��ta) -� (3��ta +� 2 ��tc)
3��tc +� 4 ��ta =� c1, 3��ta +� 2��tc =� c2
T (n) =� n��c1-� c2 ł� n �� W� (T (n)) =� W� (n)
prawdziwe dla każdego
ne"c2/(c1-1) i c1>1 i c2>0
29/45
Wyznaczanie złożoności obliczeniowej
algorytmów rekurencyjnych
metoda iteracyjna zależność rekurencyjna
przedstawiana w postaci sumy składników
zależnych od n i warunków brzegowych, dla
uproszczenia obliczeń problem przestawia się
często w postaci tzw. drzewa rekursji
metoda podstawiania polega na odgadnięciu
rozwiązania i udowodnieniu go indukcyjnie wraz z
obliczeniem odpowiednich stałych
metoda rekurencji uniwersalnej
wykorzystuje twierdzenie o rekurencji uniwersalnej,
rozważane 3 przypadki
30/45
Złożoność obliczeniowa funkcji n!
definicja matematyczna wyrażenia n!
0! = 1
n! = n"(n-1)!
n jest liczbą naturalną, n e" 1
31/45
Złożoność obliczeniowa funkcji n! (2)
int fun_silnia(int n)
{
int silnia;
if(n==0) silnia=1;
else silnia=n*fun_silnia(n-1);
return silnia;
}
main()
{
int n;
cout<<"podaj n: "; cin>>n;
cout<<"\n" <33/45
Złożoność obliczeniowa funkcji n! (4)
T(n) = tc+T(n-1)
T(n-1) = tc+T(n-2)
Wyznaczenie czasu
T(n-2) = tc+T(n-3)
wykonania zadania w
sposób nierekurencyjny:
& = &
T(1) = tc+T(0)
T(0) = tc
po sumowaniu stronami �!
T(n)+T(n-1)+& +T(0)=(n+1)"tc+T(n-1)+& +T(0)
ostatecznie
T(n) =(n+1)"tc => O(n)
34/45
Złożoność obliczeniowa algorytmu do
wyznaczania wyrazów ciągu Fibonacciego
definicja:
fib(0)=0
fib(1)=1
fib(n)=fib(n-1)+fib(n-2) dla n e" 2
pierwsze wyrazy:
0, 1, 1, 2, 3, 5, 8, 13,...
35/45
Ciąg Fibonacciego  drzewo
rekursji
T(n=5)
wierzchołki dla n=5
1
T(n-4) T(n-3)
1 1
T(n-3) T(n-2) T(n-2) T(n-1)
1
1 1 1
T(n-2) T(n-1)
1 1 1 1 1 1 1 1
36/45
Ciąg Fibonacciego  złożoność (2)
operacje  w węzłach wykonywane są 1 raz
od węzłów odchodzą co najwyżej 2 gałęzie,
symbolizujące dwa wywołania rekurencyjne, zgodnie z
definicją wyrazu ciągu Fibonacciego dla n>2
liczba poziomów: n-2 (zakładając poziom korzenia=0)
liczba węzłów na i-tym poziomie: d" 2i
liczba wszystkich węzłów równa CO NAJWYŻEJ:
n-�2
i
1 +� 2 +� 4 +� 8 +� ...+� 2n-�2 =�
��2 <� 2n �� O( 2n )
i=�0
37/45
Metoda rekurencji uniwersalnej
służy do określania klasy funkcji T(n) o równaniu:
T(n)=a"T(n/b)+f(n),
problem rozkładany jest na a
gdzie:
podproblemów o rozmiarze n/b
i koszcie podziału f(n)
a, b stałe
f(n) nierekurencyjna część równania
b
g( n ) =� nlog a
należy obliczyć wartość wyrażenia
jeżeli g(n) i f(n) są wielomianowo:
b
T (n) =� Q�(g(n)��log n) =� Q�(nlog a ��log2 n)
g(n)>f(n), to
b
T( n ) =� Q� ( g( n )) =� Q� ( nlog a )
g(n)=f(n), to
g(n)T( n ) =� Q� ( f ( n ))
38/45
Wyszukiwanie połówkowe
zastosowanie wyszukiwanie wartości w tablicy
posortowanej
efekt zmniejszenie (w porównaniu do wyszukiwania
liniowego) liczby wykonywanych operacji
algorytm:
tablica dzielona jest na dwie połówki
sprawdzane jest, w której połówce znajduje się
ewentualnie szukana wartość
wybraną połówkę dzieli się ponownie na dwie części
39/45
Wyszukiwanie połówkowe 
złożoność algorytmu
void binary_search(int tab[],int r, int szw, int l, int p)
{
if(l>p) cout<<"w tablicy nie ma szukanej wartosci!";
else
wartość dzieląca
{
na 2 połowy
int k=(l+p)/2;
if(szw==tab[k]) cout<<"szukana wartosc jest na poz."<else
{
if (szw>tab[k]) binary_search(tab,r,szw,k+1,p);
else binary_search(tab,r,szw,l,k-1);
}
poszukiwanie w
}
poszukiwanie w
prawej połówce
}
lewej połówce
40/45
Wyszukiwanie połówkowe  wyznaczanie
złożoności metodą rekurencji uniwersalnej
T(n)=1"T(n/2)+2 dzielimy tablicę na podtablice o
rozmiarze n/2, sprawdzamy tylko jedną podtablicę,
dodatkowo wykonywane są dwie operacje porównania
sprawdzanie g(n):
g(n) jest równe
wielomianowo f(n)=2
2
g(n) =� nlog 1 =� n0 =�1��
�� T (n) =� Q�(g(n)��log2 n) =� Q�(log2 n)
41/45
Porównanie wyszukiwania
liniowego i połówkowego
Liczba
120
O(n) O(log2n)
elementów
100
80
10 10 4
60
100 100 7
40
20
1000 1000 10
0
10000 10000 14
0 20 40 60 80 100 120
liczba elementów
100000 100000 17
O(n) O(log2n)
1000000 1000000 20
42/45
liczba operacji
Sortowanie przez scalanie  opis
podobna do quicksort
jest metodą rekurencyjną typu
 dziel i zwyciężaj
schemat działania:
podział tablicy n-elementowej na dwie podtablice
zawierające po n/2 elementów
sortowanie metodą przez scalanie każdej podtablicy
łączenie posortowanych podtablic w jedną tablicę
43/45
Sortowanie przez scalanie -
algorytm
void sort_scalanie(int t[], int p, int k)
{
int m;
if(p{
m=(p+k)/2;
sort_scalanie(t,p,m);
sort_scalanie(t,m+1,k);
scalanie(t,n,p,m,k);
}
}
44/45
Złożoność algorytmu sortowania
przez scalanie
ogólna postać funkcji złożoności praktycznej:
T(n)=2"T(n/2)+f(n)
obie podtablice dzielenie na
scalanie podtablic,
są sortowane 2 podtablice
Ś(f(n)) = n
2
g(n) =� nlog 2 =� n1 =� n ��
�� T (n) =� Q�(g(n)��log n) =� Q�(n ��log n)
45/45
Sortowanie quicksort 
przypadek najgorszy
n n
T (n) =� T (n -�1) +� O(n) =�
n ��k O(��k) =� O(n2)
j=�1 j=�1
n operacji
1 n-1
n-1 operacji
1 n-2
1 n-3
n-2 operacji
koszty
n 1 &
& operacji
operacji
podziały na 1
1 3
4 operacje
element i
pozostałą część
1 2 3 operacje
O(n)  koszt
wydzielenia podtablic
2 operacje
1 1
46/45
Sortowanie quicksort 
przypadek najlepszy
n n
n
n/2 n/2
n/4 n/4 n/4 n/4
n
logn
n
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
&
& &
n
1 1 1 1 1 1 1
T (n) =� 2T (n / 2) +� O(n) =� O(n ��log n)
47/45
Podział klas algorytmów
P rozwiązywalne w czasie co najwyżej
wielomianowym (O(nk), kstała)
NP algorytmy niedeterministycznie wielomianowe,
których znane rozwiązanie można sprawdzić w czasie
wielomianowym
NP-zupełne (NPC) podklasa NP, algorytmy dla
których nie są znane rozwiązania w czasie
wielomianowym, ale nie udowodniono też braku ich
istnienia (trudne problemy, często decyzyjne, np.
problem komiwojażera), każdy algorytm NP można
zredukować w czasie wielomianowym do klasy Np-
zupełny
48/45
Dziękuję za uwagę
49