Złożoność czasowa algorytmu

Question

Witam
Potrzebuje pomocy w obliczeniu średniej złożoności Algorytmu.
Mamy Algorytm1() o Średniej złożoności A(n) = Θ(n^(1/2)), oraz poniższy pseudo kod:

Algorytm( int n ){
   for(i=0; i<lg(n); i++){
      Algorytm1(i)
   }
}

Zastanawiam się czy tym przypadku "i" można potraktować jako stałą c gdzie A(n) = lg(n) * Θ(c^(1/2)) =  Θ(lg(n)), czy jednak takie podejście jest błędne?
Z góry dziękuje
 

Answer 1

Nawet jeśli tak zrobisz, to błędne jest założenie A(n) = lg(n) * Θ(c^(1/2)) =  Θ(lg(n))
Dlatego, że c nie jest równe n...  a dodatkowo, stała ta jest nie większa niż lg(n)  - przy założeniu  C jako i.

 Zwróć uwagę, że to jest funkcja rekurencyjna z drugiej strony jej współczynnik rośnie Algorytm1(i) -> ale ni będzie większy niż parametr ln(n) 
Warto skorzystać z własności logarytmu naturalnego  np przy wyznaczaniu granicy 

Zauważ że: twój algotym nigdy nie bedzie większy niż graniczna funkcji  A(C) = gdzie jako C- możesz własnie przyjąć to że jeśli C -> będzie równe lg(n) dla twojego i, to zawsze dla tej wartości będzie wykres tej fynkcji większy stąd, można przyjąc że A(LG(N))  > A(n)  

ale lepiej  Logarytm naturalny liczby  można zdefiniować jako pole pod wykresem   w przedziale 1 do a