TEORETYCZNE
PODSTAWY
INFORMATYKI
Prowadzący:
ppor. mgr inż. Mariusz
CHMIELEWSKI
e-mail:
mchmiel@isi.wat.waw.pl
Temat 1:
Temat 1:
Analiza złożoności
Analiza złożoności
obliczeniowej algorytmów
obliczeniowej algorytmów
TEORETYCZNE
PODSTAWY
INFORMATYKI
Prowadzący:
ppor. mgr inż. Mariusz
CHMIELEWSKI
e-mail:
mchmiel@isi.wat.waw.pl
Temat 1:
Temat 1:
Analiza złożoności
Analiza złożoności
obliczeniowej algorytmów
obliczeniowej algorytmów
ppor. mgr inż. Mariusz CHMIELEWSKI
2
Analiza złożoności obliczeniowej
Analiza złożoności czasowej algorytmu (ang. Time complexity analysis) to
określenie liczby wykonań operacji podstawowej dla każdej wartości
rozmiaru danych wejściowych.
Zakłada się że:
-
nie uwzględniamy szczegółów implementacji algorytmu;
-
operacja
elementarna
jest
zaimplementowana
w
sposób
najwydajniejszy z możliwych;
Wybór operacji podstawowej:
-
zależy od specyfiki analizowanego algorytmu;
-
potrzeb przeprowadzanej analizy (nie uwzględnia się instrukcji
sterujących);
-
możliwość wyboru więcej niż jednej operacji podstawowej;
Rodzaje złożoności czasowej:
1.
Złożoność czasowa w każdym przypadku – every-case time complexity
2.
Złożoność czasowa w najgorszym przypadku – worst-case time
complexity
3.
Złożoność czasowa w średnim przypadku – average-case time
complexity
4.
Złożoność czasowa w najlepszym przypadku – best-case time
complexity
Złożoność czasowa algorytmów
ppor. mgr inż. Mariusz CHMIELEWSKI
3
Rodzaje złożoności czasowej
Złożoność czasowa w każdym przypadku – every-case time complexity -
T(n)
W przypadku, gdy operacja podstawowa jest zawsze wykonywana tę samą
liczbę razy dla każdej realizacji problemu o rozmiarze n.
Złożoność czasowa w najgorszym przypadku – worst-case time complexity
-
W(n)
W przypadku analizowanego algorytmu złożoność W(n) definiujemy jako
maksymalna liczbę wykonań
operacji podstawowej dla danych wejściowych o rozmiarze n.
Złożoność czasowa w średnim przypadku – average-case time complexity -
A(n)
W przypadku analizowanego algorytmu złożoność A(n) definiujemy jako
średnią (wartość oczekiwaną)
liczbę wykonań operacji podstawowej dla danych wejściowych o rozmiarze
n.
Złożoność czasowa w najlepszym przypadku – best-case time complexity -
B(n)
W przypadku analizowanego algorytmu złożoność B(n) definiujemy jako
minimalną liczbę wykonań
operacji podstawowej dla danych wejściowych o rozmiarze n.
ppor. mgr inż. Mariusz CHMIELEWSKI
4
Wyszukiwanie sekwencyjne
– przykład analizy algorytmu
Algorytm nie posiada złożoności w każdym przypadku – zależność od
rozmiaru danych n.
Złożoność czasowa w średnim przypadku
Operacja podstawowa: porównanie elementu w tablicy z x.
Rozmiar danych wejściowych: n, liczba elementów znajdujących
się w tablicy
Przypadek gdy wyszukiwany element znajduje się w tablicy
danych wejściowych:
Przypadek gdy wyszukiwany element nie znajduje się w tablicy
danych wejściowych:
n
k
n
k
n
n
n
n
k
n
n
k
n
A
1
1
2
1
2
)
1
(
1
1
1
)
(
n
k
p
p
n
p
n
n
n
n
p
p
n
n
p
k
n
A
1
2
2
1
1
2
)
1
(
1
)
(
ppor. mgr inż. Mariusz CHMIELEWSKI
5
Wyszukiwanie sekwencyjne
– przykład analizy algorytmu
Złożoność czasowa w najgorszym przypadku
Operacja podstawowa: porównanie elementu w tablicy z x.
Rozmiar danych wejściowych: n, liczba elementów
znajdujących się w tablicy
W(n) = n; przypadek kiedy ostatnim elementem w tablicy
jest element poszukiwany a więc algorytm wykona n
przebiegów
Złożoność czasowa w najlepszym przypadku
Operacja podstawowa: porównanie elementu w tablicy z x.
Rozmiar danych wejściowych: n, liczba elementów
znajdujących się w tablicy
B(n) = 1; przypadek kiedy nastąpi jedno wykonanie pętli
ponieważ wyszukiwany element znajduje się na początku
tablicy do przeszukiwania czyli x = S[1] gdzie S jest
tablicą zawierająca dane do przeszukiwania natomiast x
jest poszukiwanym elementem;
ppor. mgr inż. Mariusz CHMIELEWSKI
6
Złożoność obliczeniowa i
asymptotyczna
Złożoność obliczeniowa:
miara służąca do porównywania efektywności
algorytmów. Mamy dwa kryteria efektywności:
czas i pamięć
.
Do oceny efektywności stosujemy jednostki logiczne
wyrażające związek miedzy rozmiarem danych
(wielkość pliku lub tablicy) N a ilością czasu T
potrzebna na ich przetworzenie.
Funkcja wyrażająca zależność miedzy N a T jest
zwykle bardzo
skomplikowana, a jej obliczenie ma znaczenie
jedynie w odniesieniu do
dużych rozmiarów danych =>
przybliżona miara
efektywności czyli
tzw. złożoność asymptotyczna.
ppor. mgr inż. Mariusz CHMIELEWSKI
7
Szacowanie złożoności obliczeniowej
O z n a c z e n i a :
- a l g o r y t m r o z w i ą z u j ą c y d e c y z y j n y p r o b l e m ;
D
n
-
z b i ó r d a n y c h r o z m i a r u n d l a r o z w a ż a n e g o p r o b l e m u ;
t ( I - l i c z b a k r o k ó w D T M p o t r z e b n a d o r o z w i ą z a n i a
k o n k r e t n e g o p r o b l e m u
n
I
D
o r o z m i a r z e
n
z
N
p r z y
p o m o c y a l g o r y t m u
D e fi n i c j a
Z ł o ż o n o ś c i ą o b l i c z e n i o w ą ( p e s y m i s t y c z n ą ) a l g o r y t m u
n a z y w a m y f u n k c j ę p o s t a c i
( 1 )
n
I
I
W
D
:
t
n
α
max
ppor. mgr inż. Mariusz CHMIELEWSKI
8
SZACOWANIE ZŁOŻONOŚCI
OBLICZENIOWEJ
D e fi n i c j a
M ó w i m y ,
ż e
a l g o r y t m
m a z ł o ż o n o ś ć o b l i c z e n i o w ą
w i e l o m i a n o w ą , j e ś l i i s t n i e j e s t a ł a c > 0 o r a z w i e l o m i a n p ( n ) t a k i e ,
ż e :
n
cp
n
α
n
n
0
W
c o z a p i s u j e m y
n
p
O
n
α
W
.
W i n n y c h p r z y p a d k a c h m ó w i m y , ż e a l g o r y t m m a z ł o ż o n o ś ć
w y k ł a d n i c z ą .
ppor. mgr inż. Mariusz CHMIELEWSKI
9
Definicja rzędów złożoności obliczeniowej
Niech R* =R
+
{0}.
Mówimy,
że
funkcja
f(x):R* R* jest rzędu
1
O(g(x)) (g(x):R* R*), jeśli
istnieje taka stała c>0 oraz
x
0
R*, że dla każdego xx
0
zachodzi f(x)cg(x) (f nie
rośnie szybciej niż g).
1
x
y
x
0
f(x)
cg(x)
f(x)=O(g(x))
[1]
0.
c
pewnego
dla
)
(
)
(
lim
gdy
)),
(
(
)
(
x
c
x
g
x
f
x
g
O
x
f
ppor. mgr inż. Mariusz CHMIELEWSKI
10
Definicja rzędów złożoności obliczeniowej
Mówimy,
że
funkcja
f(x):R* R* jest rzędu
2
(g(x)) (g(x):R* R*), jeśli
istnieje taka stała c>0 oraz
x
0
R*, że dla każdego xx
0
zachodzi g(x)cf(x) (f nie
rośnie wolniej niż g).
x
y
x
0
cf(x)
g(x)
[2]
.
0
)
(
)
(
lim
lub
)
(
)
(
lim
gdy
)),
(
(
)
(
x
x
c
x
g
x
f
x
g
x
f
x
g
x
f
ppor. mgr inż. Mariusz CHMIELEWSKI
11
Definicja rzędów złożoności obliczeniowej
Mówimy,
że
funkcja
f(x):R* R* jest rzędu
(g(x))
(g(x):R* R*),
jeśli istnieją takie stałe c
1
,
c
2
>0 oraz x
0
R*, że dla
każdego xx
0
zachodzi
c
1
g(x)f(x)c
2
g(x)
(f rośnie tak samo jak g).
x
y
x
0
f(x)
c
1
g(x)
c
2
g(x)
Jeżeli funkcja f(x) jest O(
g(x)) oraz (g(x)), to jest (g(x)) .
ppor. mgr inż. Mariusz CHMIELEWSKI
12
Graficzna ilustracja notacji
ppor. mgr inż. Mariusz CHMIELEWSKI
13
Definicja rzędów złożoności obliczeniowej
P r a k t y c z n e p r z y k ł a d y d e fi n i c j i r z ę d ó w
2 |s i n x | = O ( l o g x ) ,
2 |s i n x | = O ( 1 )
x
3
+ 5 x
2
+ 2 = O ( x
3
) o r a z x
3
+ 5 x
2
+ 2 = ( x
3
) , w i ę c
x
3
+ 5 x
2
+ 2 = ( x
3
)
f ( x ) = x
2
+ b x + c = ( x
2
) ,
g d y ż
a
c
a
b
x
x
|
|
,
|
|
max
2
0
z a c h o d z i :
c
1
g ( x ) f ( x ) c
2
g ( x ) d l a
a
c
4
1
1
,
a
c
4
7
2
, g ( x ) = x
2
)1
(
1
1
2
O
x
,
1
0
x
x
o r a z n p . d l a c 1 ;
x ! = O ( x
x
) ,
1
0
x
x
o r a z n p . d l a c 1 .
ppor. mgr inż. Mariusz CHMIELEWSKI
14
Własności funkcji rzędów złożoności
obliczeniowej
Własność 1 (przechodniość):
Jeśli f(n) jest O(g(n)) i g(n) jest O(h(n)), to f(n) jest
O(h(n)).
Własność 2:
Jeśli f(n) jest O(h(n)) i g(n) jest O(h(n)), to f(n)+g(n) jest
O(h(n)).
Własność 3:
Funkcja an
k
jest O(n
k
).
Własność 4:
Funkcja n
k
jest O(n
k+j
) dla dowolnego dodatniego j.
Z tych wszystkich własności wynika, ze dowolny
wielomian jest „duże O” dla n podniesionego do
najwyższej w nim potęgi, czyli
f(n) = a
k
n
k
+ a
k-1
n
k-1
+ ..... + a
1
n
+a
0
jest O(n
k
) (jest
też oczywiście O(n
k+j
) dla dowolnego dodatniego j).
ppor. mgr inż. Mariusz CHMIELEWSKI
15
Własności funkcji rzędów złożoności
obliczeniowej
Własność 5:
Własność 5:
Jeśli f(n)=c g(n), to f(n) jest O(g(n)).
Jeśli f(n)=c g(n), to f(n) jest O(g(n)).
Własność 6:
Własność 6:
Funkcja log
Funkcja log
a
a
n jest O(log
n jest O(log
b
b
n) dla dowolnych a i b większych
n) dla dowolnych a i b większych
niż 1.
niż 1.
Własność 7:
log
a
n jest O(log
2
n) dla dowolnego dodatniego a.
Jedną z najważniejszych funkcji przy ocenianiu
efektywności algorytmów
jest funkcja logarytmiczna.
Jeżeli można wykazać że złożoność algorytmu jest
rzędu logarytmicznego, algorytm można traktować
jako bardzo dobry. Istnieje wiele funkcji lepszych niż
logarytmiczna, jednak zaledwie kilka spośród nich, jak
O(log
2
log
2
n) czy O(1) ma praktyczne znaczenie.
ppor. mgr inż. Mariusz CHMIELEWSKI
16
Wymagany czas obliczeń dla
algorytmów różnej złożonosci
ppor. mgr inż. Mariusz CHMIELEWSKI
17
Własności funkcji rzędów złożoności
obliczeniowej - Przykład
P r z y k ł a d 2
D z i a ł a n i a n a f u n k c j a c h r z ę d ó w z ł o ż o n o ś c i , n p . :
)
(
)
(
2
1
3
2
2
2
2
n
n
n
n
n
P i e r w s z e z r ó w n a ń m ó w i , ż e i s t n i e j e p e w n a f u n k c j a f ( n ) ( n )
t a k a , ż e
)
(
2
1
3
2
2
2
n
f
n
n
n
d l a w s z y s t k i c h n .
D r u g i e , ż e d l a k a ż d e j f u n k c j i g ( n ) ( n ) i s t n i e j e p e w n a f u n k c j a
h ( n ) ( n
2
)
t a k a ,
ż e
)
(
)
(
2
2
n
h
n
g
n
d l a
w s z y s t k i c h
n .
Z i n t e r p r e t a c j i t e j w y n i k a , ż e
)
(
1
3
2
2
2
n
n
n
.
ppor. mgr inż. Mariusz CHMIELEWSKI
18
Własności funkcji rzędów złożoności obliczeniowej
Własności funkcji rzędów złożoności obliczeniowej
potencjalne problemy
potencjalne problemy
Celem wprowadzonych wcześniej sposobów zapisu (notacji) jest
porównanie
efektywności
rozmaitych
algorytmów
zaprojektowanych do rozwiązania tego samego problemu.
Jeżeli będziemy stosować tylko notacje „wielkie O” do
reprezentowania
złożoności algorytmów, to niektóre z nich możemy
zdyskwalifikować
zbyt
pochopnie.
Załóżmy, że mamy dwa algorytmy rozwiązujące pewien
problem, wykonywana przez nie liczba operacji to odpowiednio
10
8
n i 10n
2
.
Pierwsza funkcja jest O(n), druga O(n
2
).
Opierając się na informacji dostarczonej przez notacje „wielkie
O” odrzucilibyśmy drugi algorytm, ponieważ funkcja kosztu
rośnie zbyt szybko.
Spełnione jest to jednak dla odpowiednio dużych n, ponieważ
dla n<10
7
drugi algorytm wykonuje mniej operacji niż
pierwszy !!!.
Istotna jest więc tez stała (10
8
), która w tym przypadku jest
zbyt duża, aby notacja była znacząca.
ppor. mgr inż. Mariusz CHMIELEWSKI
19
Metody mierzenia czasu działania
algorytmu
Sposób pomiaru ilości pracy wykonanej przez algorytm powinien
zapewniać:
porównanie efektywności dwóch różnych algorytmów rozwiązujących ten
sam problem;
oszacowanie faktycznej wydajności metody, abstrahując od komputera,
języka programowania, umiejętności programisty i szczegółów
technicznych implementacji (sposobu inkrementacji zmiennych
sterujących pętli, sposobu obliczania indeksów zmiennych ze
wskaźnikami itp.);
WNIOSEK:
Dobrym przybliżeniem czasochłonności algorytmu jest
obliczenie liczby przejść przez
wszystkie pętle w algorytmie
.
ppor. mgr inż. Mariusz CHMIELEWSKI
20
Oszacowanie złożoności algorytmu -
wytyczne
W praktyce zlicza się tzw. operacje podstawowe dla badanego
problemu lub klasy rozważanych algorytmów, tj. takie, które są
najczęściej wykonywane (ignorując pozostałe operacje pomocnicze,
takie jak instrukcje inicjalizacji, instrukcje organizacji pętli itp.).
Ponieważ większość programów to programy złożone z wielu
modułów lub podprogramów, a w każdym takim podprogramie inna
instrukcja może grać rolę operacji podstawowej, więc fragmenty
większej całości analizuje się zwykle oddzielnie i na podstawie
skończonej liczby takich modułów szacuje się czasochłonność
algorytmu jako całości.
ppor. mgr inż. Mariusz CHMIELEWSKI
21
SZACOWANIE ZŁOŻONOŚCI
OBLICZENIOWEJ
Jak mierzyć czas działania algorytmu?, c.d.
Jak mierzyć czas działania algorytmu?, c.d.
Tabela 1 Przykłady operacji podstawowych dla
typowych problemów obliczeniowych
Lp.
Problem
Operacja
1.
2.
3.
4.
Znalezienie x na liście
nazwisk.
Mnożenie dwóch macierzy
liczb rzeczywistych.
Porządkowanie liczb.
Wyznaczanie drogi
najkrótszej w grafie zadanym
w postaci listy sąsiadów.
Porównanie x z pozycją na
liście.
Mnożenie dwóch macierzy
liczb typu real (lub mnożenie
i dodawanie).
Porównanie dwóch liczb
(lub porównanie i zamiana).
Operacja na wskaźniku listy.
ppor. mgr inż. Mariusz CHMIELEWSKI
22
SZACOWANIE ZŁOŻONOŚCI
OBLICZENIOWEJ
Jak mierzyć czas działania algorytmu?, c.d.
Jak mierzyć czas działania algorytmu?, c.d.
Zalety zliczania operacji podstawowych:
możliwość przewidywania zachowania się algorytmu dla
dużych rozmiarów danych (jeżeli łączna liczba operacji
jest proporcjonalna do liczby operacji podstawowych);
swoboda wyboru operacji podstawowej.
W skrajnym przypadku można wybrać rozkazy maszynowe konkretnego
komputera. Z drugiej strony jedno przejście przez instrukcję pętli można
również potraktować jako operację podstawową. W ten sposób możemy
manipulować stopniem precyzji w zależności od potrzeb.
ppor. mgr inż. Mariusz CHMIELEWSKI
23
Przykłady praktyczne mierzenia
złożoności obliczeniowej
Przykład 4: Prosta pętla
for (i=sum=0; i<n; i++) sum+=a[i];
Powyższa pętla powtarza się n razy, podczas każdego jej przebiegu realizuje
dwa przypisania: aktualizujące zmienną „sum” i zmianę wartości zmiennej „i”.
Mamy zatem 2n przypisań podczas całego wykonania pętli; jej
asymptotyczna złożoność wynosi O(n).
asymptotyczna złożoność wynosi O(n).
ppor. mgr inż. Mariusz CHMIELEWSKI
24
Przykłady praktyczne mierzenia
złożoności obliczeniowej
Przykład 5: Pętla zagnieżdżona
for (i=0; i<n; i++) {
for (j=1, sum=a[0]; j<=i; j++)
sum+=a[j]; }
Na samym początku zmiennej „i” nadawana jest wartość początkowa.
Pętla zewnętrzna powtarza się n razy, a w każdej jej iteracji wykonuje
się wewnętrzna pętla oraz instrukcja przypisania wartości zmiennym „i”,
„ j”, „ sum”. Pętla wewnętrzna wykonuje się „i” razy dla każdego i e
{1,...,n-1}, a na każdą iteracje przypadają dwa przypisania:jedno dla
„sum”, jedno dla „j”. Mamy zatem
1 + 3n + 2(1+2+...+n-1) = 1 + 3n + n (n-1) = O(n) + O(n
2
) = O(n
2
)
przypisań wykonywanych w całym programie.
Jej
asymptotyczna złożoność wynosi O(n
asymptotyczna złożoność wynosi O(n
2
2
).
).
Pętle zagnieżdżone mają zwykle większą złożoność niż pojedyncze,
Pętle zagnieżdżone mają zwykle większą złożoność niż pojedyncze,
jednak nie musi tak być zawsze.
jednak nie musi tak być zawsze.
ppor. mgr inż. Mariusz CHMIELEWSKI
25
Przykłady praktyczne mierzenia
złożoności obliczeniowej
Analiza tych dwóch przypadków była stosunkowo prosta ponieważ
liczba iteracji nie zależała od wartości elementów tablicy.
Wyznaczenie złożoności asymptotycznej jest trudniejsze jeżeli
liczba iteracji nie jest zawsze jednakowa.
Przykład 6: Znajdź najdłuższą podtablicę zawierającą
liczby uporządkowane rosnąco.
for (i=0; len=1; i<n-1; i++) {
for (i1=i2=k=i; k<n-1 && a[k]<a[k+1]; k++,i2++);
if(len < i2-i1+1) len=i2-i1+1; }
=> Jeśli liczby w tablicy są uporządkowane malejąco, to pętla zewnętrzna
wykonuje się n-1 razy, a w każdym jej przebiegu pętla wewnętrzna
wykona się tylko raz. Złożoność algorytmu jest więc
O(n).
O(n).
ppor. mgr inż. Mariusz CHMIELEWSKI
26
Przykłady praktyczne mierzenia
złożoności obliczeniowej
Analiza tych dwóch przypadków była stosunkowo prosta ponieważ
liczba iteracji nie zależała od wartości elementów tablicy.
Wyznaczenie złożoności asymptotycznej jest trudniejsze jeżeli
liczba iteracji nie jest
zawsze jednakowa.
Przykład 6: Znajdź najdłuższą podtablicę zawierającą
liczby uporządkowane rosnąco.
for (i=0; len=1; i<n-1; i++) {
for (i1=i2=k=i; k<n-1 && a[k]<a[k+1]; k++,i2++);
if(len < i2-i1+1) len=i2-i1+1; }
Jeśli liczby w tablicy są uporządkowane rosnąco, to pętla zewnętrzna wykonuje się
n-1 razy, a w każdym jej przebiegu pętla wewnętrzna wykona się i razy dla i {1,...,n-1}.
Złożoność algorytmu jest więc
O(n
O(n
2
2
).
).
ppor. mgr inż. Mariusz CHMIELEWSKI
27
Przykłady praktyczne mierzenia
złożoności obliczeniowej
Analiza tych dwóch przypadków była stosunkowo prosta ponieważ
liczba iteracji nie zależała od wartości elementów tablicy.
Wyznaczenie złożoności asymptotycznej jest trudniejsze jeżeli
liczba iteracji nie jest
zawsze jednakowa.
Przykład 6: Znajdź najdłuższą podtablicę zawierającą
liczby uporządkowane rosnąco.
for (i=0; len=1; i<n-1; i++) {
for (i1=i2=k=i; k<n-1 && a[k]<a[k+1]; k++,i2++);
if(len < i2-i1+1) len=i2-i1+1; }
=> Z reguły dane nie są uporządkowane i ocena złożoności algorytmu jest
rzeczą niełatwą, ale bardzo istotną. Staramy się wyznaczy złożoność
w „przypadku optymistycznym”, „przypadku pesymistycznym” oraz
„przypadku średnim”.
ppor. mgr inż. Mariusz CHMIELEWSKI
28
Sortowanie stabilne
Definicja:
Metoda sortowania jest stabilna, jeśli
zachowuje względną kolejność elementów o
jednakowych kluczach.
Oznaczenia : sortujemy tablicę:
ElemType a[n];
Definiujemy funkcję
replaceElements( x, y)
,która zamienia wartości dwóch elementów
ppor. mgr inż. Mariusz CHMIELEWSKI
29
Sortowanie bąbelkowe (bubblesort)
for (i = n-1; i>=1 ; i--)
for (j = 0 ; j<=i-1 ; j++)
if (a[j]>a[j+1])
replaceElements (a[j],a[j+1]);
Idea działania:
w i-tej iteracji, kolejne zamiany w zakresie a[0..i-1] powodują, że największy spośród elementów
w a[0..i-1] trafia na miejsce o indeksie "i-1"; iteracja jest powtarzana dla i=n-1,n-2,...,1.
Złożoność:
Operacjami dominującymi są porównania a[j]>a[j+1]. Jest ich:
(n-1) + (n-2) + . . . + 1 = n*(n-1) / 2
Zatem pesymistyczna złożoność czasowa wynosi
T(n) = 1/2 * n
2
– 1/2 * n
T(n) = 1/2 * n
2
+ O(1)
T(n) = O(n
2
)
Złożoność średnia: identyczna jak pesymistyczna.
Czyli: liczba porównań pesymistycznie i średnio ok. 1/2 n
2
.
Metoda jest stabilna.
ppor. mgr inż. Mariusz CHMIELEWSKI
30
Sortowanie przez wybieranie
for (i = 0; i< (n-1); i++){
min = i ;
for (j = i+1; j<=n-1; j++)
if (a[j] < a[min]) min := j;
replaceElements ( a[i], a[min] );
}
Idea:
w i-tym kroku znajdź najmniejszy element spośród a[i . .n-1] i zamień go z
elementem a[i]; powtarzaj ten krok dla i=0,...,n-2
Złożoność: identycznie jak dla metody bąbelkowej
T(n) = O(n
2
)
Czyli: zarówno w pesymistycznym, jak i średnim przypadku, liczba
porównań wynosi ok. 1/2 n
2
.
Zalety:
Wykonuje tylko n-1 zamian (istotne dla długich rekordów)
Sortowanie metodą selekcji nie jest stabilne.
ppor. mgr inż. Mariusz CHMIELEWSKI
31
Sortowanie przez wstawianie
for (i = 1; i< n; i++){
j = i-1;
tmp = a[i];
while ((j >= 0)&&(tmp < a[j])){
a[j+1]=a[j];
j=j-1;
}
a[j+1] = tmp;
}
Idea: W i-tym kroku wstaw element a[i] na właściwe miejsce w posortowanym fragmencie a[0 . . i-
1], wcześniej przesuwając wszystkie elementy większe od niego w tym fragmencie w prawo o
1; powstaje posortowany fragment a[0 . . i].
Złożoność pesymistyczna (ciąg posortowany malejąco na wejściu) identyczna jak dla poprzednich
przypadków.
Średnia dwukrotnie lepsza.
w przypadku pesymistycznym ok. 1/2 n
2
porównań
w przypadku średnim ok. 1/4 n
2
porównań.
Zalety:
1. Stabilność
2. Średnio dwukrotnie szybszy niż inne proste metody
3. Optymalny dla ciągów prawie posortowanych
ppor. mgr inż. Mariusz CHMIELEWSKI
32
Przykłady praktyczne mierzenia złożoności
obliczeniowej
Przykład 7:
Algorytm sortowania
Insertion-Sort(A)
1. for j:=2 to length[A]
2. do key:=A[j]
/* Wstaw A[i] w
posortowany
ciąg A[1..j-1].*/
3. i:= j-1
4. while i>0 i A[i] > key
5. do A[i+1] := A[i]
6. i:= i-1
7. A[i+1] := key
Przykład działania
algorytmu
5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6
ppor. mgr inż. Mariusz CHMIELEWSKI
33
Przykłady praktyczne mierzenia złożoności obliczeniowej
Przykłady praktyczne mierzenia złożoności obliczeniowej
Insertion-Sort(A)
koszt
koszt
liczba wykonań
liczba wykonań
1.
for j:=2 to length[A]
c
1
n
2.
do key:=A[i]
c
2
n-1
3.
i:= j-1
c
3
n-1
4.
while i>0 i A[i] > key
c
4
5.
do A[i+1] := A[i]
c
5
6.
i:= i-1
c
6
7.
A[i+1] := key
c
7
n-1
n
j
j
t
2
n
j
j
t
2
)
1
(
n
j
j
t
2
)
1
(
ppor. mgr inż. Mariusz CHMIELEWSKI
34
Przykłady praktyczne mierzenia złożoności
obliczeniowej
)
1
(
)
1
(
)
1
(
)
1
(
)
1
(
)
(
7
2
6
2
5
2
4
3
2
1
n
c
t
c
t
c
t
c
n
c
n
c
n
c
n
T
n
j
j
n
j
j
n
j
j
1
2
)
1
(
2
n
n
j
n
j
2
)
1
(
)
1
(
2
n
n
j
n
j
)
1
(
2
)
1
(
2
)
1
(
1
2
)
1
(
)
1
(
)
1
(
)
(
7
6
5
4
3
2
1
n
c
n
n
c
n
n
c
n
n
c
n
c
n
c
n
c
n
T
)
(
2
2
2
2
2
2
7
4
3
2
7
6
5
4
3
2
1
2
6
5
4
c
c
c
c
n
c
c
c
c
c
c
c
n
c
c
c
)
(
)
(
2
2
n
c
bn
an
n
T
ppor. mgr inż. Mariusz CHMIELEWSKI
35
Algorytm sortowania metodą scalania
Analizujemy pesymistyczną złożoność czasową – operacjami dominującymi są porównania wykonywane podczas
scalania.
Załóżmy najpierw, że n jest potęgą dwójki, n = 2
k
Analiza złożoności algorytmu "dziel i zwyciężaj" za pomocą równania rekurencyjnego na liczbę operacji
dominujących.
Tutaj:
T(n) = 0, jeśli n = 1
2 T(n/2) + n , jeśli n > 1 bo:
dwa podzadania wielkości n/2,
koszt podziału pomijalny (zero porównań) ,
koszt scalania to liczba porównań podczas scalania ciągów posortowanych, równa sumie ich
długości – tutaj n.
Rozwiązanie równania rekurencyjnego: na T(n) przez iterowanie tego równania i wywnioskowanie stąd jego
ogólnej postaci:
T(n) = 2 T(n/2) + n = 2 ( 2 T(n/4) + n/2) + n = 2 ( 2 ( 2 T(n/8) + n/4 ) + n/2 ) + n =
= 2 ( . . . . 2 ( 2 T(1) + 2 ) + 4 ) + . . . . . ) + n = n log n
Inna metoda: rozrysowując drzewo wywołań rekurencyjnych. Na każdym poziomie zagnieżdżenia rekurencji liczba
porównań wynosi n, a drzewo ma wysokość log n.
Dla dowolnego n (tzn. niekoniecznie będącego potęgą dwójki) wysokość drzewa wywołań nie przekracza log n + 1.
Liczba porównań w algorytmie sortowania przez scalanie wynosi zatem:
T(n) = n log n + O(n)
Wady metody:
potrzebuje pamięci roboczej rozmiaru O(n) (złożoność pamięciowa)
traci czas na przepisywanie elementów.
ppor. mgr inż. Mariusz CHMIELEWSKI
36
Mierzenie złożoności obliczeniowej
– przydatne funkcje
2
)
1
(
0
n
n
i
n
i
1
2
2
1
0
n
n
i
i
n
n
i
i
n
2
0
1
1
1
0
x
x
x
n
n
i
i
3
)
1
)(
5
.
0
(
0
2
n
n
n
i
n
i
)
1
(
ln
1
1
O
n
i
n
i
ppor. mgr inż. Mariusz CHMIELEWSKI
37
Mierzenie złożoności obliczeniowej
– przydatne funkcje
O S Z A C O W A N I A :
J e ś li f () j e s t f u n k c j ą r o s n ą c ą , to :
1
1
)
(
)
(
)
(
b
a
b
a
i
b
a
dx
x
f
i
f
dx
x
f
J e ś li f () j e s t f u n k c j ą m a le j ą c ą , to :
b
a
b
a
i
b
a
dx
x
f
i
f
dx
x
f
1
1
)
(
)
(
)
(
ppor. mgr inż. Mariusz CHMIELEWSKI
38
KLASY I TYPY FUNKCJI ZŁOŻONOŚCI
OBLICZENIOWEJ
Klasa funkcji
Typ funkcji
Przykłady
stała
n
e
n
2
sin
,
n
/
1
subliniowa
polilogarytmiczna
n
log
log
,
n
2
log
liniowa
n
,
n
n
n
/
1
1
quasi-liniowa
n
nlog
,
n
n
log
log
wielomianowa
kwadratowa
2
n
,
2
n
superwielomianowa
n
n
lg
,
n
e
wykładnicza
n
2
,
n
n 3
2
niewielomianowa
superwykładnicza
n
n
2
,
n
n
ppor. mgr inż. Mariusz CHMIELEWSKI
39
Wpływ wzrostu prędkości komputera na
maksymalny rozmiar zagadnienia, które można
rozwiązać w jednostce czasu
Algorytm
Maksymalny rozmiar zagadnienia
Symbol
Złożoność
przed wzrostem
prędkości
po 100-krotnym
wzroście prędkości
5
A
n
N
5
5
100N
4
A
2
n
N
4
10 N
4
3
A
3
n
N
3
4.64 N
3
2
A
5
n
N
2
3.5 N
2
1
A
n
2
N
1
6.64+N
1
0
A
n
nlog
N
0
0
100N dla
1
0
N
h
N 1
2
4
,
100
1
2
4
4
h
N
c
10
100
4
c
h
N
1
2
1
,
100
1
2
1
1
h
c
N
100
2
1
c
c
1
=
lo
g
2
1
0
0
=
6
.6
4
ppor. mgr inż. Mariusz CHMIELEWSKI
40
Przykład postępu, jaki dokonał się w
dziedzinie projektowania algorytmów
badających planarność grafu
A lgo rytm
R o zm ia r
a na lizo w a neg o
gra fu
w przyp a dku
udo stęp nia nia
ko m putera na
o kres
Sym bo l
A uto r [ ro k] Z ło żo no ść
C za s o bliczeń
dla
ms
c
10
100
n
m inuty go dziny
1
A
K urato w sk i
[19 30]
6
cn
325 lat
4
8
2
A
G o ldstein
[19 63]
3
cn
2.8 go dz in
18
71
3
A
L em pel et al.
[19 67]
2
cn
100 sek und
77
6 0 00
4
A
H o pcro ft-
T arjan [197 1]
n
cn
2
log
7 sek und
643
24 6 73
5
A
H o pcro ft-
T arjan [197 4]
cn
1 sek unda
6 000
4
10
36
ppor. mgr inż. Mariusz CHMIELEWSKI
41
Związek pomiędzy rzędem złożoności, stałą
proporcjonalności, rozmiarem danych i rzeczywistym
czasem obliczeń na minikomputerze i superkomputerze
n
C
r
a
y
-1
3
3
n [n
s
]
P
E
N
T
IU
M
IV
1
.6
G
H
z
1
9
5
0
0
0
n
[n
s
]
1
0
3
μ
s
3
0
0
μ
s
1
0
0
3
m
s
3
m
s
1
0
0
0
3
s
3
0
m
s
1
0
0
0
0
4
9
m
in
.
3
0
0
m
s
1
0
0
0
0
0
0
9
5
la
t
3
s
M
im
o
ż
e
a
lg
o
r
y
t
m
s
z
e
ś
c
ie
n
n
y
„
w
y
s
t
a
r
t
o
w
a
ł”
z
w
ię
k
s
z
y
m
im
p
e
t
e
m
,
d
r
u
g
i a
lg
o
r
y
t
m
(
lin
io
w
y
)
, m
a
ją
c
y
z
ło
ż
o
n
o
ś
ć
o
2
r
z
ę
d
y
n
iż
s
z
ą
(
O
(
n
)
w
s
t
o
s
u
n
k
u
d
o
O
(
n
3
)
)
,
„
d
o
g
o
n
ił g
o
”
i o
k
a
z
a
ł s
ię
s
z
y
b
s
z
y
d
la
100
n
.