Krzysztof Pancerz

Algorytmika i struktury danych

Algorytmy 

i

struktury danych

WYKŁ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:  

i mówimy, że funkcja f(n) jest co najwyżej rzędu 

g(n) jeśli istnieją stałe c>0 oraz n

0

 takie, że:

Mówimy, że g jest asymptotycznym ograniczeniem 

górnym dla f.

f

n=Og n

f

nc⋅g n dla każdego nn

0 

 

Krzysztof Pancerz

Algorytmika i struktury danych

Notacja O (cd.)

●

Przykład

dla każdego n≥1, możemy przyjąć c=13 oraz n

0

=1. Stąd: 

f

n=10 n

2

2 n1

10 n

2

2 n1 10 n

2

2 n

2

n

2

=13 n

2

10 n

2

2 n1 =O n

2



 

Krzysztof Pancerz

Algorytmika i struktury danych

Notacja Ω

●

f , g – funkcje o wartościach nieujemnych określone 
w dziedzinie nieujemnych liczb całkowitych. 
Piszemy:

i mówimy, że funkcja f(n) jest co najmniej rzędu 

g(n) jeśli istnieją stałe c>0 oraz n

0

 takie, że:

Mówimy, że g jest asymptotycznym ograniczeniem 

dolnym dla f.

f

n=g n

f

nc⋅g n dla każdego nn

0 

 

Krzysztof Pancerz

Algorytmika i struktury danych

Notacja Ω (cd.)

●

Przykład

dla każdego n≥1, możemy przyjąć c=10 oraz n

0

=1. Stąd: 

f

n=10 n

2

2 n1

10 n

2

2 n1 10 n

2

10 n

2

2 n1 =n

2



 

Krzysztof Pancerz

Algorytmika i struktury danych

Notacja θ

●

f , g – funkcje o wartościach nieujemnych określone 
w dziedzinie nieujemnych liczb całkowitych. 
Piszemy:  

i mówimy, że f(n) jest dokładnie rzędu g(n) jeśli 

istnieją stałe c

1

>0, c

2

>0 oraz n

0

 takie, że:

Mówimy, że g jest asymptotycznym dokładnym 

oszacowaniem dla f.

f

n=g n

c

1 

⋅g n f nc

2 

⋅g n dla każdego nn

0 

 

Krzysztof Pancerz

Algorytmika i struktury danych

Notacja θ (cd.)

●

Przykład

 

Ponieważ:

oraz

więc

f

n=10 n

2

2 n1

10 n

2

2 n1 =On

2



10 n

2

2 n1 =n

2



10 n

2

2 n1 =n

2



 

Krzysztof Pancerz

Algorytmika i struktury danych

Ograniczenia asymptotyczne

 

Krzysztof Pancerz

Algorytmika i struktury danych

Ograniczenia asymptotyczne (cd.)

●

Twierdzenie

Niech

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=a

k

n

k

a

k

−1

n

k

−1

...a

1 

n

a

0

p

n=n

k



 

Krzysztof Pancerz

Algorytmika i struktury danych

Ograniczenia asymptotyczne (cd.)

●

Inne zależności:

log n

n dla każdego n1

1

2...n=n

2



log n!

=n log n

∑

i

=1

n

1 

i

=log n

 

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(n

2

)

●

Złożoności wielomianowe O(n

3

), O(n

4

), ...

●

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

n

)

●

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(n

2

)

100 μs

10 ms

1 s

O(2

n

)

10 ms

3,17•10

7 

lat

 

Krzysztof Pancerz

Algorytmika i struktury danych

Oszacowanie złożoności

●

Przykład

 n – rozmiar danych wejściowych.

n

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

t

n=10 n

2

2 n1

10 n

2

2 n1

10 n

2

 

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<n; 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)

 x=0∧ y=m∧m0∧n0∧ y0

[ x=m− yn]∧[ y0 ]

[ x=m− yn]∧[ y=0 ]⇒[ x=mn]

Przykład