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

Question

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) ?

Answer 1

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.

Comments

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))  ??

---

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.