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