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)