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

Złożoność O(log n)

Object Storage Arubacloud
0 głosów
1,442 wizyt
pytanie zadane 1 lipca 2018 w Algorytmy przez poldeeek Mądrala (5,980 p.)
Witam, mam pytanie jak sprawdzić czy jakieś złożoności są równe złożoności O(log n) ? Generalnie wiem, że relacji f(x)=O(g(x)), trzeba znaleźć takie c, żeby dla dowolnego n>=n0 zachodziło f(x)<=c*g(x), tylko że nie potrafię rozpisać tego dla przypadków kiedy sprawdzam takie równanie z logarytmem... Gdyby ktoś mógł rozpisać mi jak to sie dokładnie liczy np. dla n^(1/2) = O(log n) ?

1 odpowiedź

+2 głosów
odpowiedź 1 lipca 2018 przez 99xkubax99 Obywatel (1,780 p.)
wybrane 1 lipca 2018 przez poldeeek
 
Najlepsza
Witaj,

Ogólnie ciężko Ci będzie wykazać, że n^(1/2) = O(log n), ponieważ funkcja pierwiastek z n ma większe tempo wzrostu niż funkcja log2(n). Możesz to zobaczyć, dla przykładu poprzez policzenie pochodnej pierwiastka  z n (jest to 1/2 * n^-1/2) oraz pochodnej log2(n); jest to 1/nln2. Tak więc przy n -> +inf mianownik pochodnej log2(n) zwiększa się bardziej niż pochodnej n^1/2, więc cały ułamek pochodnej pierwiastka z x będzie rósł szybciej, zatem tempo wzrostu funkcji f(n) = n^1/2 będzie większe. Tak więc o ile nie udowodnisz tego dla przykładu n^(1/2) = O(log n), to funkcja log n mogłaby być za  to dolnym ograniczeniem funkcji pierwiastek z n, przed chwilą pokazałem, że log n rośnie wolniej, więc mógłby być dolnym ograniczeniem dla n^1/2. Tak więc: n^(1/2) = Ω(log n). ​​​​​​Musimy więc dobrać takie c, i n0 takie, aby dla każdego n>n0 było prawdziwe n^(1/2)>= clog n. Dla c = 1/2 prawa strona tej nierówności przyjmuje postać 1/2 log n, więc log(n^1/2). Wiadomo, że dla takiego c funkcja n^(1/2) rośnie szybciej niż log (n^1/2). Aby to było spełnione wystarczy wybrać n0 = 0.
komentarz 1 lipca 2018 przez poldeeek Mądrala (5,980 p.)
edycja 1 lipca 2018 przez poldeeek
Czyli jeśli dobrze rozumiem, sposobem na ten logarytm jest zmiana obu funkcji na ich pochodne i dla nich szukać takich c i n0 ? Zakładając, że zdanie będzie odwrotne, czyli czy (log n) = O(n^(1/2)), bo teoretycznie to chyba spełnia tę relację, to musiałbym zamienić funkcje na ich pochodne i szukać takiego c, które w tym przypadku spełni nierówność 1/n = c/(2*n^(1/2))  ??
1
komentarz 1 lipca 2018 przez 99xkubax99 Obywatel (1,780 p.)
To równanie spełnia tą relację, ponieważ jeżeli jedna funkcja jest dolnym ograniczeniem dla drugiej, to jest to równoważne, że druga jest górnym ograniczeniem dla tej pierwszej. Przykład z pochodnymi przytoczyłem w celu, aby pokazać, że funkcja logarytm z n nie może być górnym ograniczeniem dla funkcji pierwiastek z n z powodu wolniejszego tempa wzrostu. Nie ma uniwersalnego sposobu na wyznaczanie odpowiedniego c, jeżeli np ograniczeniem funkcji jest funkcja wielomianowa, to c może mieć postać 2^k, a tutaj jak widać wystarczy zauważyć, że spełnia to c=1/2.

Podobne pytania

0 głosów
1 odpowiedź 943 wizyt
+1 głos
0 odpowiedzi 342 wizyt

92,674 zapytań

141,575 odpowiedzi

320,045 komentarzy

62,038 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!

...