Algorytmy
i
struktury danych
WYKA
AD 2
Dr inż. Krzysztof Pancerz
Krzysztof Pancerz
Algorytmika i struktury danych
Notacja O

f , g  funkcje o wartościach nieujemnych określone
w dziedzinie nieujemnych liczb całkowitych.
Piszemy:
f śąnźą=Ośąg śąnźąźą
i mówimy, że funkcja f(n) jest co najwyżej rzędu
g(n) jeśli istnieją stałe c>0 oraz n0 takie, że:
f śąnźąąąc�"g śąnźą dla każdego n�ąn0
Mówimy, że g jest asymptotycznym ograniczeniem
górnym dla f.
Krzysztof Pancerz
Algorytmika i struktury danych
Notacja O (cd.)

Przykład
f śąnźą=10 n2�ą2 n�ą1
10 n2�ą2 n�ą1 ąą10 n2�ą2 n2�ąn2=13 n2
dla każdego ne"1, możemy przyjąć c=13 oraz n0=1. Stąd:
10 n2�ą2 n�ą1 =O śąn2źą
Krzysztof Pancerz
Algorytmika i struktury danych
Notacja �

f , g  funkcje o wartościach nieujemnych określone
w dziedzinie nieujemnych liczb całkowitych.
Piszemy:
f śąnźą=śąśąg śąnźąźą
i mówimy, że funkcja f(n) jest co najmniej rzędu
g(n) jeśli istnieją stałe c>0 oraz n0 takie, że:
f śąnźą�ąc�"g śąnźą dla każdego n�ąn0
Mówimy, że g jest asymptotycznym ograniczeniem
dolnym dla f.
Krzysztof Pancerz
Algorytmika i struktury danych
Notacja � (cd.)

Przykład
f śąnźą=10 n2�ą2 n�ą1
10 n2�ą2 n�ą1 �ą10 n2
dla każdego ne"1, możemy przyjąć c=10 oraz n0=1. Stąd:
10 n2�ą2 n�ą1 =śąśąn2źą
Krzysztof Pancerz
Algorytmika i struktury danych
Notacja �

f , g  funkcje o wartościach nieujemnych określone
w dziedzinie nieujemnych liczb całkowitych.
Piszemy:
f śąnźą=�ąśąg śąnźąźą
i mówimy, że f(n) jest dokładnie rzędu g(n) jeśli
istnieją stałe c1>0, c2>0 oraz n0 takie, że:
c1 �"g śąnźąąą f śąnźąąąc2 �"g śąnźą dla każdego n�ąn0
Mówimy, że g jest asymptotycznym dokładnym
oszacowaniem dla f.
Krzysztof Pancerz
Algorytmika i struktury danych
Notacja � (cd.)

Przykład
f śąnźą=10 n2�ą2 n�ą1
Ponieważ:
10 n2�ą2 n�ą1 =Ośąn2źą
oraz
10 n2�ą2 n�ą1 =śąśąn2źą
więc
10 n2�ą2 n�ą1 =�ąśąn2źą
Krzysztof Pancerz
Algorytmika i struktury danych
Ograniczenia asymptotyczne
Krzysztof Pancerz
Algorytmika i struktury danych
Ograniczenia asymptotyczne (cd.)

Twierdzenie
Niech
pśąnźą=ak nk�ąak-1 nk-1�ą...�ąa1 n�ąa0
będzie wielomianem stopnia k o wartościach dodatnich (tj.
p(n)>0 dla każdego n) określonym w dziedzinie
nieujemnych liczb całkowitych. Wówczas:
pśąnźą=�ąśąnkźą
Krzysztof Pancerz
Algorytmika i struktury danych
Ograniczenia asymptotyczne (cd.)

Inne zależności:
log nąąn dla każdego n�ą1
1�ą2�ą...�ąn=�ąśąn2źą
log n!=�ąśąn log nźą
n
1 =�ąśąlog nźą
"
i
i=1
Krzysztof Pancerz
Algorytmika i struktury danych
Złożoność obliczeniowa algorytmów (cd.)

Złożoność obliczeniowa algorytmu określana
jest przez zasoby systemu komputerowego
(przede wszystkim czas działania i ilość
zajmowanej pamięci) niezbędne do realizacji
algorytmu.

Rodzaje złożoności obliczeniowej:

złożoność czasowa,

złożoność pamięciowa.

Złożoność obliczeniowa (czasowa i
pamięciowa) algorytmu podawana jest jako
funkcja rozmiaru danych wejściowych n.
Krzysztof Pancerz
Algorytmika i struktury danych
Złożoność obliczeniowa algorytmów

Przy określaniu złożoności czasowej
uwzględnia się tzw. operacje dominujące
(podstawowe) w algorytmie.

Rodzaje złożoności czasowej:

pesymistyczna (złożoność w najgorszym
przypadku),

średnia (oczekiwana).
Krzysztof Pancerz
Algorytmika i struktury danych
Podstawowe złożoności obliczeniowe

Złożoność logarytmiczna O(log n)

Złożoność liniowa O(n)

Złożoność liniowo-logarytmiczna O(n log n)

Złożoność kwadratowa O(n2)

Złożoności wielomianowe O(n3), O(n4), ...

Złożoność wykładnicza O(2n)

Złożoność silnia O(n!)
Krzysztof Pancerz
Algorytmika i struktury danych
Podstawowe złożoności obliczeniowe (cd.)
n 10 100 1000
O(n) 10 źs 100 źs 1 ms
O(n2) 100 źs 10 ms 1 s
O(2n) 10 ms 3,17" 107 lat
Krzysztof Pancerz
Algorytmika i struktury danych
Oszacowanie złożoności

Przykład
t śąnźą=10 n2�ą2 n�ą1
n  rozmiar danych wejściowych.
n
10 n2�ą2 n�ą1
10 n2
10 1 021 1 000
100 100 201 100 000
1 000 10 002 001 10 000 000
10 000 1 000 020 001 1 000 000 000
Krzysztof Pancerz
Algorytmika i struktury danych
Przykład 1

Określić złożoność obliczeniową następującego
fragmentu algorytmu:
for(i=1; i<=n; i++)
{
for(j=1; j<=i; j++)
{ k=2*k; }
}
Operacja dominująca: mnożenie
Krzysztof Pancerz
Algorytmika i struktury danych
Przykład 2

Określić złożoność obliczeniową następującego
fragmentu algorytmu:
for(int i=1; i{ for(int j=n-1; j>=i; j--)
{ if(tab[j-1]>tab[j])
{
t=tab[j-1]; tab[j-1]=tab[j]; tab[j]=t;
}
}
Operacja dominująca: porównanie
}
Krzysztof Pancerz
Algorytmika i struktury danych
Trudność problemów

Problemy, dla których zaproponowano
algorytmy o złożoności wielomianowej (klasa
P).

Problemy, których trudność została
udowodniona w czasie wielomianowym (klasa
NP).

Problemy, dla których trudność nie została
udowodniona, jednak nie zaproponowano
algorytmów o złożoności wielomianowej
rozwiązujących te problemy (klasa problemów
NP-zupełnych).
Krzysztof Pancerz
Algorytmika i struktury danych
Niezmiennik instrukcji iteracyjnej (pętli)

Niezmiennik instrukcji iteracyjnej (pętli) 
warunek opisujący wartości zmiennych w
trakcie wykonywania algorytmu taki, że:

jest on spełniony na początku instrukcji iteracyjnej,

każde powtórzenie instrukcji iteracyjnej zachowuje
go,

jest on spełniony po zakończeniu instrukcji
iteracyjnej.
Krzysztof Pancerz
Algorytmika i struktury danych
Niezmiennik instrukcji iteracyjnej (pętli)
Przykład
śą x=0źą'"śą y=mźą'"śąmą0źą'"śąną0źą'"śą yą0źą
[ x=śąm- yźąn]'"[ y�ą0 ]
[ x=śąm- yźąn]'"[ y=0 ]�![ x=mn]
Krzysztof Pancerz
Algorytmika i struktury danych