Algorytmy i struktury
Algorytmy i struktury
danych
danych
Uniwersytet J.Kochanowskiego w Kielcach
Uniwersytet J.Kochanowskiego w Kielcach
Dr Zbigniew Bem
Dr Zbigniew Bem
2010 rok
2010 rok
Literatura
Literatura
" Aho A., Hopcroft J., Ullman J., Projektowanie i
" Aho A., Hopcroft J., Ullman J., Projektowanie i
analiza algorytmów komputerowych, PWN 1983,
analiza algorytmów komputerowych, PWN 1983,
Helion, 2003.
Helion, 2003.
" Banachowski L., Dikes K., Rytter W., Algorytmy i
" Banachowski L., Dikes K., Rytter W., Algorytmy i
struktury danych, WNT, 2003.
struktury danych, WNT, 2003.
" T. H. Cormen, C. E. Leiserson, C. Stein i R. L.
" T. H. Cormen, C. E. Leiserson, C. Stein i R. L.
Rivest, Wprowadzenie do algorytmów, WNT 2004.
Rivest, Wprowadzenie do algorytmów, WNT 2004.
" M. Kubale, A
agodne wprowadzenie do analizy
" M. Kubale, A
agodne wprowadzenie do analizy
algorytmów, Gdańsk 2004.
algorytmów, Gdańsk 2004.
" Wróblewski P., Algorytmy struktury danych i
" Wróblewski P., Algorytmy struktury danych i
techniki programowania, Helion 1997.
techniki programowania, Helion 1997.
Przypomnienie
Przypomnienie
Algorytm  w matematyce oraz informatyce to
Algorytm  w matematyce oraz informatyce to
skończony, uporządkowany ciąg jasno zdefiniowanych
skończony, uporządkowany ciąg jasno zdefiniowanych
czynności, koniecznych do wykonania pewnego
czynności, koniecznych do wykonania pewnego
zadania.
zadania.
Algorytm  w informatyce to skończony,
Algorytm  w informatyce to skończony,
uporządkowany ciąg jasno określonych czynności,
uporządkowany ciąg jasno określonych czynności,
przekształcający zbiór danych wejściowych w zbiór
przekształcający zbiór danych wejściowych w zbiór
danych wyjściowych (wyników) pewnego zadania.
danych wyjściowych (wyników) pewnego zadania.
� Zbigniew Bem
Algorytmy komputerowe
Komputery przetwarzają przekazywane im informacje za
Komputery przetwarzają przekazywane im informacje za
pomocą programów z wykorzystaniem algorytmów.
pomocą programów z wykorzystaniem algorytmów.
Każdy algorytm komputerowy musi być wprowadzony do
Każdy algorytm komputerowy musi być wprowadzony do
komputera w bardzo rygorystycznie zdefiniowanym
komputera w bardzo rygorystycznie zdefiniowanym
języku. Program jest algorytmem zapisanym w języku
języku. Program jest algorytmem zapisanym w języku
zrozumiałym dla maszyny.
zrozumiałym dla maszyny.
Jeżeli dany algorytm da się wykonać na maszynie o
Jeżeli dany algorytm da się wykonać na maszynie o
dostępnej mocy obliczeniowej i pamięci oraz
dostępnej mocy obliczeniowej i pamięci oraz
akceptowalnym czasie, to mówi się że jest obliczalny.
akceptowalnym czasie, to mówi się że jest obliczalny.
� Zbigniew Bem
Analiza algorytmów
Analiza algorytmów
Analiza algorytmów to dział informatyki zajmujący się
Analiza algorytmów to dział informatyki zajmujący się
szukaniem najlepszych algorytmów dla zadań
szukaniem najlepszych algorytmów dla zadań
komputerowych. Analiza algorytmów polega między
komputerowych. Analiza algorytmów polega między
innymi na:
innymi na:
1. Badaniu czy dany problem może być rozwiązany na
1. Badaniu czy dany problem może być rozwiązany na
komputerze w dostępnym czasie i z danymi zasobami
komputerze w dostępnym czasie i z danymi zasobami
pamięci?
pamięci?
2. Który ze znanych algorytmów należy zastosować w danych
2. Który ze znanych algorytmów należy zastosować w danych
okolicznościach?
okolicznościach?
3. Poszukiwaniu lepszego algorytmu od rozważnego? Który z
3. Poszukiwaniu lepszego algorytmu od rozważnego? Który z
algorytmów jest optymalny?
algorytmów jest optymalny?
4. Jak uzasadnić, że stosując dany algorytm, rozwiąże się
4. Jak uzasadnić, że stosując dany algorytm, rozwiąże się
zamierzone zadanie?
zamierzone zadanie?
� Zbigniew Bem
Teoria złożoności obliczeniowej
Teoria złożoności obliczeniowej
Głównym jej celem jest określanie ilości
Głównym jej celem jest określanie ilości
zasobów potrzebnych do rozwiązania
zasobów potrzebnych do rozwiązania
problemów obliczeniowych. Rozważanymi
problemów obliczeniowych. Rozważanymi
zasobami są takie wielkości jak czas, pamięć
zasobami są takie wielkości jak czas, pamięć
lub procesor (liczba procesorów).
lub procesor (liczba procesorów).
Teoria złożoności obliczeniowej
Teoria złożoności obliczeniowej
1 Złożoność algorytmów
1 Złożoność algorytmów
- Złożoność czasowa
- Złożoność czasowa
- Złożoność pamięciowa
- Złożoność pamięciowa
2 Porównywanie złożoności algorytmów
2 Porównywanie złożoności algorytmów
3 Klasy złożoności
3 Klasy złożoności
� Zbigniew Bem
Złożoność obliczeniowa algorytmów
Złożoność obliczeniowa algorytmów
Złożoność obliczeniową algorytmu definiuje się jako ilość
Złożoność obliczeniową algorytmu definiuje się jako ilość
zasobów komputerowych, potrzebnych do jego wykonania.
zasobów komputerowych, potrzebnych do jego wykonania.
Podstawowymi zasobami rozważanymi w analizie
Podstawowymi zasobami rozważanymi w analizie
algorytmów są czas działania i ilość zajmowanej pamięci.
algorytmów są czas działania i ilość zajmowanej pamięci.
Na złożoność obliczeniową składa się złożoność
Na złożoność obliczeniową składa się złożoność
pamięciowa i złożoność czasowa.
pamięciowa i złożoność czasowa.
Jako przykład może nam posłużyć problem rozkładu liczb
Jako przykład może nam posłużyć problem rozkładu liczb
na czynniki pierwsze. Domyślamy się, że (niezależnie od
na czynniki pierwsze. Domyślamy się, że (niezależnie od
algorytmu) im większa liczba, tym więcej zasobów będzie
algorytmu) im większa liczba, tym więcej zasobów będzie
potrzebnych do jej rozłożenia. Taką własność ma
potrzebnych do jej rozłożenia. Taką własność ma
znakomita większość problemów obliczeniowych: im
znakomita większość problemów obliczeniowych: im
większy rozmiar danych wejściowych tym więcej zasobów
większy rozmiar danych wejściowych tym więcej zasobów
(czasu, pamięci) jest potrzebnych do jego rozwiązania.
(czasu, pamięci) jest potrzebnych do jego rozwiązania.
Złożoność algorytmu jest więc funkcją rozmiaru danych
Złożoność algorytmu jest więc funkcją rozmiaru danych
wejściowych.
wejściowych.
Na ogół nie jest możliwe wyznaczenie złożoności
Na ogół nie jest możliwe wyznaczenie złożoności
obliczeniowej jako funkcji danych wejściowych
obliczeniowej jako funkcji danych wejściowych
( takich jak ciągi, tablice, drzewa czy grafy).
( takich jak ciągi, tablice, drzewa czy grafy).
Zwykle, co naturalne, z zestawem danych
Zwykle, co naturalne, z zestawem danych
wejściowych jest związany jego rozmiar.
wejściowych jest związany jego rozmiar.
Rozmiarem wejścia nazywamy cechę danych
Rozmiarem wejścia nazywamy cechę danych
wejściowych dla algorytmu, będąca zmienną
wejściowych dla algorytmu, będąca zmienną
niezależną funkcji opisującej jego złożoność
niezależną funkcji opisującej jego złożoność
obliczeniową.
obliczeniową.
Dla różnych problemów może być ona różna - na
Dla różnych problemów może być ona różna - na
przykład dla sortowania, wyszukiwania,
przykład dla sortowania, wyszukiwania,
znajdowania maksiumum i minimum rozmiarem
znajdowania maksiumum i minimum rozmiarem
danych wejściowych jest liczba elementów kolekcji
danych wejściowych jest liczba elementów kolekcji
wejściowej. Dla problemów takich jak faktoryzacja
wejściowej. Dla problemów takich jak faktoryzacja
liczb może to być na przykład wartość liczby. Z
liczb może to być na przykład wartość liczby. Z
kolei dla operacji na macierzach będzie to po prostu
kolei dla operacji na macierzach będzie to po prostu
ich wielkość.
ich wielkość.
� Zbigniew Bem
Aby móc wyznaczać złożoność obliczeniową algorytmu,
Aby móc wyznaczać złożoność obliczeniową algorytmu,
należy się umówić, w jakich jednostkach będziemy ją
należy się umówić, w jakich jednostkach będziemy ją
liczyć.
liczyć.
" W wypadku złożoności pamięciowej za jednostkę
" W wypadku złożoności pamięciowej za jednostkę
przyjmuje się zwykle słowo pamięci maszyny.
przyjmuje się zwykle słowo pamięci maszyny.
" Sytuacja jest nieco bardziej skomplikowana w wypadku
" Sytuacja jest nieco bardziej skomplikowana w wypadku
złożoności czasowej. Złożoność czasowa powinna być
złoż oności czasowej. Złożoność czasowa powinna być
własnością samego tylko algorytmu jako metody
własnością samego tylko algorytmu jako metody
rozwiązania problemu - niezależnie od komputera, języka
rozwiązania problemu - niezależnie od komputera, języka
programowania czy sposobu jego zakodowania. W tym
programowania czy sposobu jego zakodowania. W tym
celu wyróżnia się w algorytmie charakterystyczne dla
celu wyróżnia się w algorytmie charakterystyczne dla
niego operacje, nazywane operacjami dominującymi -
niego operacje, nazywane operacjami dominującymi -
takie, że łączna ich liczba jest proporcjonalna do liczby
takie, że łączna ich liczba jest proporcjonalna do liczby
wykonań wszystkich operacji jednostkowych w dowolnej
wykonań wszystkich operacji jednostkowych w dowolnej
komputerowej realizacji algorytmu.
komputerowej realizacji algorytmu.
Na przykład: dla algorytmów sortowania, za operację
Na przykład: dla algorytmów sortowania, za operację
dominującą przyjmuje się zwykle porównanie dwóch
dominującą przyjmuje się zwykle porównanie dwóch
elementów w ciągu wejściowym, a czasem też
elementów w ciągu wejściowym, a czasem też
przestawienie elementów w ciągu; dla algorytmów
przestawienie elementów w ciągu; dla algorytmów
przeglądania drzewa binarnego przyjmuje się przejście
przeglądania drzewa binarnego przyjmuje się przejście
dowiązania między węzłami w drzewie, a dla
dowiązania między węzłami w drzewie, a dla
algorytmów wyznaczania wartości wielomianu -
algorytmów wyznaczania wartości wielomianu -
operacje arytmetyczne +, -, * i /.
operacje arytmetyczne +, -, * i /.
Za jednostkę złożoności czasowej przyjmuje się
Za jednostkę złożoności czasowej przyjmuje się
wykonanie jednej operacji dominującej.
wykonanie jednej operacji dominującej.
� Zbigniew Bem
PRZYKA
AD: Znajdowanie
PRZYKA
AD: Znajdowanie
największego elementu w zbiorze
największego elementu w zbiorze
Dane wejściowe: Zbiór n liczb.
Dane wejściowe: Zbiór n liczb.
Wynik: Największy element max w danym zbiorze.
Wynik: Największy element max w danym zbiorze.
" Algorytm Max
" Algorytm Max
krok 1: przyjmij za max dowolny element ze
krok 1: przyjmij za max dowolny element ze
zbioru,
zbioru,
krok 2: dla każdego innego elementu x zbioru wykonaj:
krok 2: dla każdego innego elementu x zbioru wykonaj:
jeśli x jest większe niż max, to za max przyjmij x
jeśli x jest większe niż max, to za max przyjmij x
Złożoność
Złożoność
Liczba porównań (operacja dominująca) wykonanych w
Liczba porównań (operacja dominująca) wykonanych w
przykładzie jest o jeden mniejsza od liczby elementów w
przykładzie jest o jeden mniejsza od liczby elementów w
zbiorze n-elementowym, czyli wynosi n -1.
zbiorze n-elementowym, czyli wynosi n -1.
Przykład pokazuje, że liczba operacji podstawowych rośnie
Przykład pokazuje, że liczba operacji podstawowych rośnie
w sposób liniowo względem rozmiaru danych i dotyczy
w sposób liniowo względem rozmiaru danych i dotyczy
złożoności czasowej.
złożoności czasowej.
UWAGA
UWAGA
W podobny sposób (poprzez prostą modyfikację) możemy
W podobny sposób (poprzez prostą modyfikację) możemy
otrzymać algorytm poszukiwania najmniejszego elementu
otrzymać algorytm poszukiwania najmniejszego elementu
w danym zbiorze.
w danym zbiorze.
� Zbigniew Bem
Złożoność algorytmów
Złożoność algorytmów
Kolejnym problemem jest fakt, iż złożoność zwykle
Kolejnym problemem jest fakt, iż złożoność zwykle
nie zależy tylko i wyłącznie od rozmiaru danych, ale
nie zależy tylko i wyłącznie od rozmiaru danych, ale
może się znacznie różnić dla instancji o
może się znacznie różnić dla instancji o
identycznym rozmiarze. Dwa często spotykane
identycznym rozmiarze. Dwa często spotykane
sposoby radzenia sobie z tym problemem to: branie
sposoby radzenia sobie z tym problemem to: branie
pod uwagę przypadków najgorszych (złożoność
pod uwagę przypadków najgorszych (złożoność
pesymistyczna) i pewien sposób uśrednienia
pesymistyczna) i pewien sposób uśrednienia
wszystkich możliwych przypadków (złożoność
wszystkich możliwych przypadków (złożoność
oczekiwana).
oczekiwana).
� Zbigniew Bem
Aby określić precyzyjnie pojęcia pesymistycznej i
Aby określić precyzyjnie pojęcia pesymistycznej i
oczekiwanej złożoności czasowej, wprowadzimy
oczekiwanej zło żoności czasowej, wprowadzimy
następujące oznaczenia:
następujące oznaczenia:
Dn - zbiór zestawów danych wejściowych
Dn - zbiór zestawów danych wejściowych
rozmiaru n;
rozmiaru n;
t(d) - liczba operacji dominujących dla zestawu
t(d) - liczba operacji dominujących dla zestawu
danych wejściowych d;
danych wejściowych d;
Xn - zmienna losowa, której wartością jest t(d)
Xn - zmienna losowa, której wartością jest t(d)
dla ;
dla ;
d"D n
pnk - rozkład prawdopodobieństwa zmiennej
pnk - rozkład prawdopodobieństwa zmiennej
losowej Xn, tzn. prawdopodobieństwo, że dla
losowej Xn, tzn. prawdopodobieństwo, że dla
danych rozmiaru n algorytm wykona k operacji
danych rozmiaru n algorytm wykona k operacji
dominujących ( k e" 0 ).
dominujących ( k e" 0 ).
Rozkład prawdopodobieństwa zmiennej losowej Xn
Rozkład prawdopodobieństwa zmiennej losowej Xn
wyznacza się na podstawie informacji o zastosowaniach
wyznacza się na podstawie informacji o zastosowaniach
rozważanego algorytmu. Gdy na przykład zbiór Dn jest
rozważanego algorytmu. Gdy na przykład zbiór Dn jest
skończony, przyjmuje się często model probabilistyczny,
skończony, przyjmuje się często model probabilistyczny,
w którym każdy zestaw danych rozmiaru n może się
w którym każdy zestaw danych rozmiaru n może się
pojawić na wejściu do algorytmu z jednakowym
pojawić na wejściu do algorytmu z jednakowym
prawdopodobieństwem.
prawdopodobieństwem.
Przez pesymistyczną złożoność czasową algorytmu
Przez pesymistyczną złożoność czasową algorytmu
rozumie się funkcję
rozumie się funkcję
W (n) = sup{t(d) : d " D}
Przez oczekiwaną złożoność czasową algorytmu
Przez oczekiwaną złożoność czasową algorytmu
rozumie się funkcję
rozumie się funkcję
A(n) = kp
" nk
k e" 0
tzn. wartość oczekiwaną E(Xn) zmiennej losowej Xn
tzn. wartość oczekiwaną E(Xn) zmiennej losowej Xn
Aby stwierdzić, na ile funkcje W(n) i A(n) są
Aby stwierdzić, na ile funkcje W(n) i A(n) są
reprezentatywne dla wszystkich danych
reprezentatywne dla wszystkich danych
wejściowych rozmiaru n, rozważa się miary
wejściowych rozmiaru n, rozważa się miary
wrażliwości algorytmu:
wrażliwości algorytmu:
" miarę wrażliwości pesymistycznej, czyli
" miarę wrażliwości pesymistycznej, czyli
"(n) = sup{ t(d1) - t(d2): d1, d2 "Dn }, oraz
"(n) = sup{ t(d1) - t(d2): d1, d2 "Dn }, oraz
" miarę wrażliwo ści oczekiwanej, czyli �(n)
" miarę wrażliwości oczekiwanej, czyli �(n)
odchylenie standardowe zmiennej losowej Xn
odchylenie standardowe zmiennej losowej Xn
PRZYKA
AD: Przeszukiwanie
sekwencyjne ciągu
" Dane wejściowe: L, N, a,
" Dane wejściowe: L, N, a,
gdzie N jest liczbą naturalną N > 0,
gdzie N jest liczbą naturalną N > 0,
a jest poszukiwanym elementem,
a jest poszukiwanym elementem,
L[1..N + 1] jest tablicą, w której na miejscach
L[1..N + 1] jest tablicą, w której na miejscach
od l do N znajdują się elementy ciągu.
od l do N znajdują się elementy ciągu.
" Wynik: Zmienna logiczna p taka, że p = true
" Wynik: Zmienna logiczna p taka, że p = true
< = > a znajduje się w L[1..N]
< = > a znajduje się w L[1..N]
� Zbigniew Bem
Algorytm:
Algorytm:
begin
begin
j :=1;
j :=1;
L[N+ 1] := a;
L[N+ 1] := a;
while L[j] <> a do j : = j + l ;
while L[j] <> a do j : = j + l ;
if j < N then p : = true;
if j < N then p : = true;
end;
end;
Rozmiar danych wejściowych: n = N
Operacja dominująca: porównanie: L[j] a" a
Pesymistyczna złożoność czasowa: W(n) = n + l
Pesymistyczna wrażliwość czasowa: "(n) = n
Jaka jest oczekiwana złożoność
czasowa?
Załóżmy, że prawdopodobieństwo znalezienia a na
Załóżmy, że prawdopodobieństwo znalezienia a na
każdym z n możliwych miejsc jest takie samo i
każdym z n możliwych miejsc jest takie samo i
wiadomo, że a jest w L[1.,N], tzn. że
wiadomo, że a jest w L[1.,N], tzn. że
1
dla k= l, 2, ..., n
pnk = dla k= l, 2, ..., n
n
Wówczas
Wówczas
n n
A(n) = =
"kp = 1 "k = 1 n(n +1) n +1
nk
n n 2 2
k =1 k =1
Oczekiwana wrażliwość czasowa:
Oczekiwana wrażliwość czasowa:
2
n
1
Wariancja:
var(Xn) = =
ś# ź#
"�#k - n+1ś#
n 2
�# #
k=1
2
�# ś#
1 n(n+1)(2n+1) 2(n+1) n(n+1) n+1
ś#
ś# ź#
= - + n�# =
ś# ź#
ś# ź#
n 6 2 2 2
�# #
�# #
(n+1)(2n+1) (n+1)2 n+1 n2 -1 n2
= - = (4n+2-3n-3)= E"
6 4 12 12 12
n2
czyli
� (n) = E" 0,29n
12
Podsumowanie przykładu
Podsumowanie przykładu
Zauważmy, że zarówno funkcje wrażliwości
Zauważmy, że zarówno funkcje wrażliwości
powyższego algorytmu, jak i funkcje jego
powyższego algorytmu, jak i funkcje jego
złożoności są liniowe; wynika stąd duża
złożoności są liniowe; wynika stąd duża
wrażliwość liczby operacji dominujących na
wrażliwość liczby operacji dominujących na
dane wejściowe.
dane wejściowe.
Metoda  dziel i zwyciężaj
Metoda  dziel i zwyciężaj
Jak było powiedziane w wykładzie 2 jedną z
Jak było powiedziane w wykładzie 2 jedną z
zasad tworzenia algorytmów jest postępowanie
zasad tworzenia algorytmów jest postępowanie
dziel i zwyciężaj (ang. divide and conquer)
dziel i zwyciężaj (ang. divide and conquer)
polegające na podzieleniu problem na kilka
polegające na podzieleniu problem na kilka
mniejszych a te znowu dzielimy, aż ich
mniejszych a te znowu dzielimy, aż ich
rozwiązania staną się oczywiste.
rozwiązania staną się oczywiste.
� Zbigniew Bem
Przykład: Znajdowanie jednocześnie
Przykład: Znajdowanie jednocześnie
największego i najmniejszego elementu
największego i najmniejszego elementu
w zbiorze.
w zbiorze.
Aby znalez
ć rozpiętość zbioru n liczb, wystarczy
Aby znalez
ć rozpiętość zbioru n liczb, wystarczy
odszukać wśród nich maksimum i minimum, a potem
odszukać wśród nich maksimum i minimum, a potem
obliczyć ich różnicę. Możemy w tym celu zastosować
obliczyć ich różnicę. Możemy w tym celu zastosować
algorytmy Max i Min. W każdym z nich liczba
algorytmy Max i Min. W każdym z nich liczba
porównań wynosi n -l, a więc rozpiętość zbioru n
porównań wynosi n -l, a więc rozpiętość zbioru n
liczb można obliczyć, wykonując 2n -2 porównania.
liczb można obliczyć, wykonując 2n -2 porównania.
Czy liczbę działań można zmniejszyć? Jak to
Czy liczbę działań można zmniejszyć? Jak to
możemy zrobić?
możemy zrobić?
Podpowiedz
: zastosować metodę  dziel i zwyciężaj
Podpowiedz
: zastosować metodę  dziel i zwyciężaj
Klasy złożoności
Klasy złożoności
Klasa złożoności to zbiór problemów obliczeniowych
Klasa złożoności to zbiór problemów obliczeniowych
o podobnej złożoności obliczeniowej - innymi słowy
o podobnej złożoności obliczeniowej - innymi słowy
problemy do których rozwiązania potrzebna jest
problemy do których rozwiązania potrzebna jest
podobna ilość zasobów łączymy w klasy.
podobna ilość zasobów łączymy w klasy.
Przykładowo mówimy o problemach o liniowej
Przykładowo mówimy o problemach o liniowej
złożoności pamięciowej, jeśli ilość potrzebnej
złożoności pamięciowej, jeśli ilość potrzebnej
pamięci rośnie liniowo względem rozmiaru danych;
pamięci rośnie liniowo względem rozmiaru danych;
czy też o problemach o kwadratowej złożoności
czy też o problemach o kwadratowej złożoności
czasowej, jeśli liczba operacji podstawowych rośnie z
czasowej, jeśli liczba operacji podstawowych rośnie z
kwadratem rozmiaru danych. Podobne określenia
kwadratem rozmiaru danych. Podobne określenia
stosujemy do algorytmów.
stosujemy do algorytmów.
Złożoność obliczeniowa
Złożoność obliczeniowa
Faktyczna złożoność algorytmu w chwili jego
Faktyczna złożoność algorytmu w chwili jego
użycia jako programu różni się od wyliczonej
użycia jako programu ró żni się od wyliczonej
teoretycznie współczynnikiem proporcjonalności,
teoretycznie współczynnikiem proporcjonalności,
który zależy od konkretnej realizacji tego
który zależy od konkretnej realizacji tego
algorytmu. Istotną zatem częścią informacji, która
algorytmu. Istotną zatem częścią informacji, która
jest zawarta w funkcjach złożoności W(n) i A(n),
jest zawarta w funkcjach złożoności W(n) i A(n),
jest ich rząd wielkości, czyli ich zachowanie
jest ich rząd wielkości, czyli ich zachowanie
asymptotyczne, gdy n dąży do nieskończoności.
asymptotyczne, gdy n dąży do nieskończoności.
Zwykle staramy się podać jak najprostszą funkcję
Zwykle staramy się podać jak najprostszą funkcję
charakteryzującą rząd wielkości W(n) i A(n) na
charakteryzującą rząd wielkości W(n) i A(n) na
przykład n, nlogn, n2, n3.
przykład n, nlogn, n2, n3.
Notacja wielkie-O
Notacja wielkie-O
Załóżmy, że f(n) i g(n) są funkcjami argumentu
Załóżmy, że f(n) i g(n) są funkcjami argumentu
całkowitego n, które dla wszystkich n przyjmują
całkowitego n, które dla wszystkich n przyjmują
wartości dodatnie (ale niekoniecznie całkowite).
wartości dodatnie (ale niekoniecznie całkowite).
Mówimy, że f (n) = O(g(n)) (lub krócej f = O(g)),
Mówimy, że f (n) = O(g(n)) (lub krócej f = O(g)),
jeżeli istnieje stała C taka, że dla wszystkich n
jeżeli istnieje stała C taka, że dla wszystkich n
liczba f (n) jest mniejsza niż C � g(n).
liczba f (n) jest mniejsza niż C � g(n).
Na przykład 2n2 + 3n - 3 = O (n2). Nietrudno
Na przykład 2n2 + 3n - 3 = O (n2). Nietrudno
bowiem pokazać, że lewa strona jest mniejsza niż
bowiem pokazać, że lewa strona jest mniejsza niż
3n2, tak więc za C możemy przyjąć 3.
3n2, tak więc za C możemy przyjąć 3.
W praktyce, używając notacji wielkie-O, nie interesujemy
W praktyce, używając notacji wielkie-O, nie interesujemy
się zachowaniem funkcji f i g dla małych wartości
się zachowaniem funkcji f i g dla małych wartości
argumentu n.
argumentu n.
" DEFINICJA
" DEFINICJA
Mówimy, że f jest co najwyżej rzędu g , co
Mó wimy, że f jest co najwyżej rzędu g , co
zapisujemy jako f(n) = O(g(n)), jeśli istnieją
zapisujemy jako f(n) = O(g(n)), jeśli istnieją
stała rzeczywista C > O i stała naturalna n0
stała rzeczywista C > O i stała naturalna n0
takie, że nierówność f(n) d" Cg(n) zachodzi dla
takie, że nierówność f(n) d" Cg(n) zachodzi dla
każdego n e" n0
każdego n e" n0
Chociaż w zapisie f = O (g) używamy znaku równości,
Chociaż w zapisie f = O (g) używamy znaku równości,
to powinniśmy o nim myśleć jako o swoistej
to powinniśmy o nim myśleć jako o swoistej
nierówności. Na przykład zapis n"n = O (n2) jest
nierówności. Na przykład zapis n"n = O (n2) jest
poprawny, podczas gdy zapis n2 = O(n"n ) jest błędny.
poprawny, podczas gdy zapis n2 = O(n"n ) jest błędny.
W praktyce będziemy używali notacji f = O (g)
W praktyce będziemy używali notacji f = O (g)
tylko wówczas, gdy funkcja g(n) jest prostsza niż
tylko wówczas, gdy funkcja g(n) jest prostsza niż
funkcja f (n) i nie rośnie zbyt szybko w
funkcja f (n) i nie rośnie zbyt szybko w
porównaniu z funkcją f (n).
porównaniu z funkcją f (n).
Inaczej mówiąc, funkcja g(n) powinna dobrze
Inaczej mówiąc, funkcja g(n) powinna dobrze
oddawać charakter wzrostu funkcji f (n), być jej
oddawać charakter wzrostu funkcji f (n), być jej
 bardzo bliskim ograniczeniem górnym".
 bardzo bliskim ograniczeniem górnym".
Następujące stwierdzenia, jakkolwiek
Następujące stwierdzenia, jakkolwiek
matematycznie poprawne, nie są użyteczne w
matematycznie poprawne, nie są użyteczne w
praktyce: (1) n2 = O(n3 + n2lnn + 6683);
praktyce: (1) n2 = O(n3 + n2lnn + 6683);
2
en );
(2) n2 = O( );
(2) n2 = O(
(3) e-n = O(n2).
(3) e-n = O(n2).
Przypuśćmy, że f (n) jest sumą składników, spośród
Przypuśćmy, że f (n) jest sumą składników, spośród
których jeden jest dla duż ych n znacznie większy
których jeden jest dla dużych n znacznie większy
niż pozostałe. Jeżeli przez g(n) oznaczymy ten
niż pozostałe. Jeżeli przez g(n) oznaczymy ten
 dominujący składnik", to możemy napisać
 dominujący składnik", to możemy napisać
f (n) = O(g(n)).
f (n) = O(g(n)).
Jeśli na przykład f (n) jest dowolnym wielomianem
Jeśli na przykład f (n) jest dowolnym wielomianem
stopnia 3 (z dodatnim współczynnikiem przy
stopnia 3 (z dodatnim współczynnikiem przy
najwyższej potędze), to f (n) = O(n3). Podobnie,
najwyższej potędze), to f (n) = O(n3). Podobnie,
jeżeli f (n) jest wielomianem stopnia d (gdzie d jest
jeżeli f (n) jest wielomianem stopnia d (gdzie d jest
ustaloną stałą, a współczynnik ad przy nd jest
ustaloną stałą, a współczynnik ad przy nd jest
dodatni), to f (n) = O(nd). Jednomian adnd jest
dodatni), to f (n) = O(nd). Jednomian adnd jest
 składnikiem dominującym".
 składnikiem dominującym".
" Jeżeli dla zadanej funkcji f (n) znajdziemy  dobrą
" Jeżeli dla zadanej funkcji f (n) znajdziemy  dobrą
funkcję g(n), tzn. wybierzemy prostą funkcję g(n),
funkcję g(n), tzn. wybierzemy prostą funkcję g(n),
dla której f = O (g) i g nie rośnie zbyt szybko w
dla której f = O (g) i g nie rośnie zbyt szybko w
porównaniu z f, to możemy użyć funkcji g, aby zdać
porównaniu z f, to możemy użyć funkcji g, aby zdać
sobie sprawę, jak zachowuje się warto ść funkcji f(n)
sobie sprawę, jak zachowuje się wartość funkcji f(n)
przy dużym wzroście argumentu n. Ze stwierdzenia
przy dużym wzroście argumentu n. Ze stwierdzenia
f (n) = O (n) możemy na przykład wywnioskować,
f (n) = O (n) możemy na przykład wywnioskować,
że  jeżeli argument n podwoi się, to wartość funkcji
że  jeżeli argument n podwoi się, to wartość funkcji
f (n) także z grubsza podwoi się".
f (n) także z grubsza podwoi się".
Z kolei ze stwierdzenia f = O (n2
) możemy
Z kolei ze stwierdzenia f = O (n2
) możemy
wnioskować, że  jeśli n podwoi się, to wartość f (n)
wnioskować, że  jeśli n podwoi się, to wartość f (n)
zwiększy się mniej więcej 4 razy". Analogicznie
zwiększy się mniej więcej 4 razy". Analogicznie
stwierdzenie f (n) = O(n3) powinno mówić, że f (n)
stwierdzenie f (n) = O(n3) powinno mówić, że f (n)
wzrośnie mniej więcej 8 razy.
wzrośnie mniej więcej 8 razy.
" Stwierdzenie f (n) = O (2n) możemy interpretować
" Stwierdzenie f (n) = O (2n) możemy interpretować
nast ępująco:  jeśli zwiększymy n o l, to wartość f (n) w
następująco:  jeśli zwiększymy n o l, to wartość f (n) w
przybliżeniu podwoi się".
przybliżeniu podwoi się".
" Jeżeli f (n) i g(n) są dwoma funkcjami, które dla n e" n0
" Jeżeli f (n) i g(n) są dwoma funkcjami, które dla n e" n0
przyjmują wartości dodatnie i jeśli ponadto
przyjmują wartości dodatnie i jeśli ponadto
f (n)
lim = const
n "
g (n)
to nietrudno pokazać, że f = O (g).
to nietrudno pokazać, że f = O (g).
� Zbigniew Bem
" Czasami będziemy chcieli bardziej precyzyjnie określić
" Czasami będziemy chcieli bardziej precyzyjnie określić
stosunek między wielkościami f (n) a g(n). Może się na
stosunek między wielkościami f (n) a g(n). Może się na
przykład zdarzyć, że gdy n dąży do nieskończoności, to
przykład zdarzyć, że gdy n dąży do nieskończoności, to
procentowy błąd, jaki popełniamy przybliżając funkcję
procentowy błąd, jaki popełniamy przybliżając funkcję
f funkcją g , dąży do zera. Występuje to wówczas, gdy
f funkcją g , dąży do zera. Występuje to wówczas, gdy
f (n)
lim = 1
n "
g (n)
W tym wypadku piszemy f " g i mówimy, że  f i g są
W tym wypadku piszemy f " g i mówimy, że  f i g są
asymptotycznie równe dla dużych n".
asymptotycznie równe dla dużych n".
� Zbigniew Bem
" DEFINICJA
" DEFINICJA
Mówimy, że f jest dokładnie rzędu g, co zapisujemy
Mówimy, że f jest dokładnie rzędu g, co zapisujemy
jako f(n) = Ś(g(n)), jeśli zarówno f(n) = O(g (n)), jak
jako f(n) = Ś(g(n)), jeśli zarówno f(n) = O(g(n)), jak
i g(n) = O(f(n)). Poprawny jest też termin f jest
i g(n) = O(f(n)). Poprawny jest też termin f jest
asymptotycznie równoważne g i oznaczamy
asymptotycznie równoważne g i oznaczamy
f " g .
f " g .
Przykład:
Przykład:
n2 + 2n " n2, bo zarówno n2 + 2n d" 3n2, jak i
n2 + 2n " n2, bo zarówno n2 + 2n d" 3n2, jak i
n2 + 2n e" n2 dla każdego n > 0.
n2 + 2n e" n2 dla każdego n > 0.
Najczęściej spotykane funkcje
Najczęściej spotykane funkcje
złożoności obliczeniowej.
złożoności obliczeniowej.
Funkcje te są uszeregowane w kolejności
Funkcje te są uszeregowane w kolejności
wzrastającej, im szybszy wzrost funkcji tym
wzrastającej, im szybszy wzrost funkcji tym
większa złożoność algorytmu.
większa złożoność algorytmu.
" logn - złożoność logarytmiczna
" logn - złożoność logarytmiczna
Czas dzia łania logarytmiczny występuje na
Czas działania logarytmiczny występuje na
przykład dla algorytmów poszukiwania
przykład dla algorytmów poszukiwania
binarnego w ciągu uporządkowanym .
binarnego w ciągu uporządkowanym .
" n - złożoność liniowa
" n - złożoność liniowa
Czas działania liniowy występuje na
Czas działania liniowy występuje na
przykład dla algorytmów, w których jest
przykład dla algorytmów, w których jest
wykonywana pewna stała liczba działań dla
wykonywana pewna stała liczba działań dla
każdego z n elementów danych
każdego z n elementów danych
wejściowych. Przykładem takiego
wejściowych. Przykładem takiego
algorytmu jest algorytm Hornera
algorytmu jest algorytm Hornera
wyznaczania wartości wielomianu.
wyznaczania wartości wielomianu.
" nlogn - złożoność nlogn (liniowo-logarytmiczna)
" nlogn - złożoność nlogn (liniowo-logarytmiczna)
Czas działania nlogn występuje na przykład dla
Czas działania nlogn występuje na przykład dla
algorytmów typu: zadanie rozmiaru n zostaje
algorytmów typu: zadanie rozmiaru n zostaje
sprowadzone do dwóch podzadań rozmiaru n/2 plus
sprowadzone do dwóch podzadań rozmiaru n/2 plus
pewna liczba działań, liniowa względem rozmiaru n,
pewna liczba działań, liniowa względem rozmiaru n,
potrzebnych do wykonania najpierw rozbicia, a
potrzebnych do wykonania najpierw rozbicia, a
następnie scalenia rozwiązań rozmiaru n/2 w
następnie scalenia rozwiązań rozmiaru n/2 w
rozwiązanie rozmiaru n. W ten sposób działa mergesort
rozwiązanie rozmiaru n. W ten sposób działa mergesort
" n2 - złożoność kwadratowa
" n2 - złożoność kwadratowa
Czas działania kwadratowy występuje na przykład dla
Czas działania kwadratowy występuje na przykład dla
algorytmów, w których jest wykonywana pewna stała
algorytmów, w których jest wykonywana pewna stała
liczba działań dla każdej pary elementów danych
liczba działań dla każdej pary elementów danych
wejściowych (podwójna instrukcja iteracyjna).
wejściowych (podwójna instrukcja iteracyjna).
" n3, n4, ... - złożoności wielomianowe
" n3, n4, ... - złożoności wielomianowe
2
" nlogn = 2log n - złożoność podwykładnicza
- złożoność podwykładnicza
"
" 2n - złożoność wykładnicza 2n ( ogólnie cn dla
" 2n - złożoność wykładnicza 2n ( ogólnie cn dla
c >1 )
c >1 )
Czas działania 2n ma na przykład algorytm, w
Czas działania 2n ma na przykład algorytm, w
którym jest wykonywana stała liczba działań dla
którym jest wykonywana stała liczba działań dla
każdego podzbioru danych wejściowych.
każdego podzbioru danych wejściowych.
" n! - złożoność n silnia
" n! - złożoność n silnia
Czas dział ania n! ma na przykład algorytm, w
Czas działania n! ma na przykład algorytm, w
którym jest wykonywana stała liczba działań dla
którym jest wykonywana stała liczba działań dla
każdej permutacji danych wejściowych.
każdej permutacji danych wejściowych.
Odrębnym zagadnieniem jest związek
Odrębnym zagadnieniem jest związek
pomiędzy złożonością algorytmu a jego
pomiędzy złożonością algorytmu a jego
przydatnością do określonych celów. Algorytm
przydatnością do określonych celów. Algorytm
o złożoności wielomianowej czy nawet
o złożoności wielomianowej czy nawet
wykładniczej może być wystarczający w
wykładniczej może być wystarczający w
sporadycznym wykorzystaniu, z drugiej strony
sporadycznym wykorzystaniu, z drugiej strony
w przetwarzaniu dużej ilości danych, nawet
w przetwarzaniu dużej ilości danych, nawet
złożoność liniowa może być problematyczna
złożoność liniowa może być problematyczna
Oczekiwany czas realizacji przykładowych
Oczekiwany czas realizacji przykładowych
algorytmów dla różnego rozmiaru danych.
algorytmów dla różnego rozmiaru danych.
Komputer wykonuje milion t.j.106 operacji w
Komputer wykonuje milion t.j.106 operacji w
ciągu sekundy.
ciągu sekundy.
n=10 n=20 n=30 n=40 n=50
n3 0,001 s 0,008 s 0,027 s 0,064 s 0,125 s
2n 0,001 s 1,05 s 17,9 m 1,27 d 35,7 lat
3n 0,059 s 58,1 m 6,53 lat 3,86*105 2,28*1010
n! 3,63 s 7,71*104 l 8,41*1018 2,59*1034 9,64*1050
Złożoność wykładnicza
Złożoność wykładnicza
Algorytm o złożoności wykładniczej może być
Algorytm o złożoności wykładniczej może być
zrealizowany jedynie dla małych rozmiarów danych.
zrealizowany jedynie dla małych rozmiarów danych.
Istnieje próg, od którego funkcja wykładnicza zaczyna
Istnieje próg, od którego funkcja wykładnicza zaczyna
rosnąć tak szybko, że realizacja algorytmu na
rosnąć tak szybko, że realizacja algorytmu na
komputerze staje się niemożliwa.
komputerze staje się niemożliwa.
Załóżmy na przykład, że dla danych rozmiaru n jest
Załóżmy na przykład, że dla danych rozmiaru n jest
wykonywanych 2n operacji jednostkowych i że każda
wykonywanych 2n operacji jednostkowych i że każda
operacja jednostkowa zajmuje odpowiednio 10-6 i 10-9
operacja jednostkowa zajmuje odpowiednio 10-6 i 10-9
sekund na dwóch różnych komputerach. Czas działania
sekund na dwóch różnych komputerach. Czas działania
potrzebny do realizacji algorytmu jest przedstawiony
potrzebny do realizacji algorytmu jest przedstawiony
w tabeli
w tabeli
Porównanie czasów realizacji algorytmu wykładniczego na
Porównanie czasów realizacji algorytmu wykładniczego na
dwóch komputerach
dwóch komputerach
Rozmiar n 20 50 100 200
Rozmiar n 20 50 100 200
Czas działania 1,04 35,7 4 �" 1014 5 �" l 044
Czas działania 1,04 35,7 4 �" 1014 5 �" l 044
(2n/106) sek lat wieków wieków
(2n/106) sek lat wieków wieków
Czas działania 0,001 13 4�"1011 5 �" 1041
Czas działania 0,001 13 4�"1011 5 �" 1041
(2n /109) sek dni wieków wieków
(2n /109) sek dni wieków wieków
Widać, że nawet 1000-krotne przyspieszenie szybkości
Widać, że nawet 1000-krotne przyspieszenie szybkości
działania komputera niewiele pomaga algorytmowi
działania komputera niewiele pomaga algorytmowi
wykładniczemu. Nierealizowalność uważa się za
wykładniczemu. Nierealizowalność uważa się za
wewnętrzną cechę algorytmu o złożoności
wewnętrzną cechę algorytmu o złożoności
wykładniczej.
wykładniczej.
Aby jednak mieć pełny obraz sytuacji, powinniśmy
Aby jednak mieć pełny obraz sytuacji, powinniśmy
jeszcze rozważyć wrażliwość algorytmu na dane
jeszcze rozważyć wraż liwość algorytmu na dane
wejściowe. Dla danego algorytmu dla którego W(n) =
wejściowe. Dla danego algorytmu dla którego W(n) =
22 + O(1) oraz "(n) = 22 + O(1), nie możemy
22 + O(1) oraz "(n) = 22 + O(1), nie możemy
twierdzić, że algorytm jest nierealizowalny dla
twierdzić, że algorytm jest nierealizowalny dla
reprezentatywnych danych. Dane wejściowe, dla
reprezentatywnych danych. Dane wejściowe, dla
których czas działania jest wykładniczy, mogą się
których czas działania jest wykładniczy, mogą się
nigdy nie pojawić w rzeczywistych okolicznościach!
nigdy nie pojawić w rzeczywistych okolicznościach!
Właśnie taka sytuacja zachodzi dla metody simplex
Właśnie taka sytuacja zachodzi dla metody simplex
programowania liniowego. Choć metoda ta ma
programowania liniowego. Choć metoda ta ma
złożoność wykładniczą dla  najgorszych" danych, lecz
złożoność wykładniczą dla  najgorszych" danych, lecz
dla pojawiających się w praktyce danych wejściowych
dla pojawiających się w praktyce danych wejściowych
działa w czasie wielomianowym, a nawet liniowym.
działa w czasie wielomianowym, a nawet liniowym.