Algorytmy003

Algorytmy rekurencyjne

aby rozwiązać problem wywołują same siebie (jeden lub więcej razy) przy rozwiązywaniu podobnych podproblemów

Etapy metody „dziel i zwyciężaj”: dziel

dzielimy problem na pewną liczbę podproblemów, stanowiących mniejsze egzemplarze tego samego problemu.

Etapy metody „dziel i zwyciężaj: zwyciężaj

rozwiązujemy podproblemy rekurencyjnie; jeśli rozmiary podproblemów są dostatecznie małe, to rozwiązujemy podproblemy bezpośrednio.

Etapy metody „dziel i zwyciężaj: połącz

łączymy rozwiązania podproblemów w rozwiązanie pierwotnego problemu.

Etapy metody „dziel i zwyciężaj: Sortowanie przez scalanie

Dziel: dzielimy n-elementowy ciąg na dwa podciągi po n/2 elementów kaŜdy. ZwycięŜaj: Sortujemy otrzymane podciągi, uzywając rekurencyjnie sortowania przez scalanie. Połącz: Łączymy posortowane podciągi w jeden posortowany ciąg.

Co charakteryzuje efektywność algorytmu?

Rząd wielkości funkcji opisującej czas działania algorytmu

Asymptotyczna złożoność obliczeniowa

wyznaczenie jedynie rzędu wielkości czasu działania algorytmu – interesuje nas, jak szybko wzrasta czas działania algorytmu, gdy rozmiar danych dąŜy do nieskończoności

Do opisu asymptotycznego czasu działania algorytmów korzysta się z

funkcji, których zbiorem argumentów jest zbiór liczb naturalnych:

Pesymistyczny czas działania T(n) jest zazwyczaj

funkcją rozmiaru danych wejściowych

Notację asymptotyczną moŜna równieŜ stosować do

funkcji charakteryzujących pewne inne aspekty algorytmów (np. ilość uŜywanej pamięci)

f(n) = O(g(n))

a<=b

f(n) = Omega(g(n))

a>=b

f(n) = Omikron(g(n))

a=b

f(n)=o(g(n))

a<b

f(n)=w(g(n))

a>b