• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Złożoność czasowa algorytmu

Object Storage Arubacloud
0 głosów
696 wizyt
pytanie zadane 1 listopada 2020 w Matematyka, fizyka, logika przez BlinkyShay Obywatel (1,190 p.)

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
 

1 odpowiedź

+1 głos
odpowiedź 1 listopada 2020 przez Wiciorny Ekspert (273,730 p.)

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 {\displaystyle \ln a=\lim _{x\to 0}{\frac {a^{x}-1}{x}}.} 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 a można zdefiniować jako pole pod wykresem {\displaystyle f(x)={\frac {1}{x}}}  w przedziale 1 do a {\displaystyle \ln(a)=\int \limits _{1}^{a}{\frac {1}{x}}\ \mathrm {d} x}Logarytm naturalny ln(x) jako całka po funkcji 1/x

 

Podobne pytania

0 głosów
1 odpowiedź 973 wizyt
0 głosów
5 odpowiedzi 2,404 wizyt
pytanie zadane 20 października 2015 w Algorytmy przez starzec Początkujący (410 p.)

92,755 zapytań

141,677 odpowiedzi

320,422 komentarzy

62,100 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...