TEORETYCZNE

PODSTAWY

INFORMATYKI

Prowadzący:

ppor. mgr inż. Mariusz

CHMIELEWSKI

e-mail:

[e-mail]

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 xx

0

zachodzi f(x)cg(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 xx

0

zachodzi g(x)cf(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 xx

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

.