Analiza czasu algorytmu

0

Poszukuję jakiegoś artykułu bądź kogoś na tym forum kto byłby w stanie wytłumaczyć mi jak analizować czas algorytmów.
Jakie operacje zabierają ile czasu i jak to wszystko na koniec połączyć?

Dając jako przykład algorytm

Mult(x,y)
if |x|=|y|=1 return xy
EXTRACT XL, YL, XR, YR
A= XL, YL
B= XR, YR
Z=(XL + XR)(YL + YR) - A - D
return 2nA2n/2*Z + D

Na koniec wychodzi że T(n)<= 3T(n/2)+O(n)

Na jakiej podstawie mam rozpoznawać jakie operacje zajmują n czasu, jakie c, a jakie n2, jakie (n-1) itd. i jak na koniec to wszystko podsumować? Wystarczy tylko dodać?

Wiem że później do T(n) można użyć twierdzenia o rekurencji uniwersalnej i zamienić na O(nlogba)
Ale co zrobić jeżeli wyjdzie mi coś czego twierdzenie nie obejmuje? Coś jak na przykład T(n)=T(n-1)+O(1)

0

Akurat jakieś T(n)=T(n-1)+O(1) to można sobie indukcyjnie udowodnić że jest liniowe ;)
T(n) = T(n-1)+O(1) = T(n-2)+2O(1) = ... = T(0) + nO(1)

Pozostałej części pytania nie rozumiem za bardzo. Musisz policzyć ile zajmuje jakiś algorytm.

0

Nie liczysz ile czasu zajmuje poszczególna instrukcja. Przy liczeniu złożoności algorytmu musisz wyznaczyć jak asymptotycznie rośnie ilość kroków, instrukcji dominujących. Musisz znaleźć funkcję w zależności od n(w różnych algorytmach może to znaczyć długość tablicy, wielkość liczby wejściowej, zależy), albo na oko oszacować ilość kroków zależności od n i stwierdzić jakiej klasy jest ta funkcja(najczęściej w notacji dużego O). Np. jak masz algorytm w którym główną częścią jest pętla iterująca po tablicy długości n, a reszta to luźne instrukcje to od razu widać, że ilość instrukcji będzie funkcją liniową czyli klasy O(n) itd. Odsyłam do książki "Wprowadzenie do algorytmów" Cormena - tam masz ładnie wszystko opisane, łącznie aparatem matematycznym do liczenia złożoności

1 użytkowników online, w tym zalogowanych: 0, gości: 1