rachunek asymptotyczny

[natkoza]

czy \(\displaystyle{ f(n)=O(g(n))}\) lub \(\displaystyle{ g(n)=O(f(n))}\) gdy:

a) \(\displaystyle{ f(n)=n+logn,g(n)=nlogn}\)
b) \(\displaystyle{ f(n)=n^{2009},g(n)=e^n}\)
c) \(\displaystyle{ f(n)=lg(n+1),g(n)=lnn}\)
d) \(\displaystyle{ f(n)=2009n^2,g(n)=n^3-n^2+n}\)

??

prosiłabym o odpowiedź wraz z krótkim uzasadnieniem

[hubertwojtowicz]

Def.
\(\displaystyle{ O(g(n))=\{f(n):}\)istnieją dodatnie stałe \(\displaystyle{ c}\) i \(\displaystyle{ n_0}\), takie że \(\displaystyle{ 0 \le f(n) \le cg(n)}\) dla wszystkich \(\displaystyle{ n \ge n_0\}}\)

a)
Sprawdzamy:
\(\displaystyle{ O(g(n))=f(n)}\)
musi zajść nierówność:
\(\displaystyle{ 0 \le f(n) \le cg(n)}\)
\(\displaystyle{ 0 \le n+logn \le cnlogn}\) (w informatyce zapis \(\displaystyle{ log x}\) równoważy \(\displaystyle{ log_2 x}\))
\(\displaystyle{ 0 \le log2^n+logn \le cnlogn}\)
\(\displaystyle{ 0 \le log(n2^n) \le cnlogn}\)
\(\displaystyle{ 0 \le log(n2^n) \le logn^{cn}}\), (z monotoniczności logarytmów) to jest prwada
\(\displaystyle{ \Leftrightarrow 0 \le n2^n \le n^{cn}}\)
dla \(\displaystyle{ n \ge n_0}\)
Teraz należy pokazać, że istnieje takie c i n. Na oko widać, że to zachodzi, zatem relacja \(\displaystyle{ O(g(n))=f(n)}\) jest prawdziwa.
Pozostałe analogiczne sprawdzasz

[111sadysta]

jak reszte uzasadnić?
np z logarytmami