[Teoria złożoności] Asymptotyczny stopień złożoności

[zxcvbnmqwertyuiop]

Jak obliczyć złożoność asymptotyczną, aby je później posortować rosnąco:

\(\displaystyle{ \sum_{k=0}^{n} k \sqrt{k}}\)
\(\displaystyle{ \frac{n^3}{7 \cdot \left( \log _{2} \left( n \right) \right) ^7}}\)
\(\displaystyle{ \frac{n^2+2}{\log _{2} \left( n \right) }}\)

ćwiczenie jest ze strony

łatwiejsze przykłady sobie obliczyłem tych nie potrafię zrobić dlatego proszęo pomoc

[bartek118]

Trzeba opracować dobre oszacowania. Na przykład
\(\displaystyle{ \frac{n^2 + n}{2}= \sum_{k=0}^{n} k \leq \sum_{k=0}^{n} k \sqrt{k} \leq \sum_{k=0}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}}\)
Zatem ta złożoność to \(\displaystyle{ O(n^3)}\) oraz \(\displaystyle{ \Omega (n^2)}\). Być może takie wystarczy do uszeregowania z pozostałymi, a być może trzeba znaleźć lepsze.

Widzimy na przykład, że
\(\displaystyle{ \frac{n^2+2}{\log _{2} \left( n \right) } \leq n^2 + 2}\)
więc jest to złożoność \(\displaystyle{ O(n^2)}\). Wynika stąd, że na pewno nie będzie gorsza od tej sumy powyżej.

[Dasio11]

Należy wiedzieć, że

\(\displaystyle{ \sum_{k=1}^n k^{\alpha} = \Theta \left( n^{\alpha+1} \right)}\)

dla \(\displaystyle{ \alpha > -1,}\) więc na przykład

\(\displaystyle{ \sum_{k=1}^{n} k \sqrt{k} = \Theta \left( n^2 \sqrt{n} \right).}\)

Ponadto dla dowolnych \(\displaystyle{ \alpha, \beta > 0}\) jest

\(\displaystyle{ \log^{\alpha} n = o( n^{\beta} ).}\)


Porównajmy dla przykładu

\(\displaystyle{ \sum_{k=1}^{n} k \sqrt{k} \qquad \text{ vs } \qquad \frac{n^3}{7 ( \log_2 n )^7}.}\)

Wiemy, że lewa strona jest tego samego rzędu, co \(\displaystyle{ n^2 \sqrt{n}.}\)

Po prawej stronie występuje logarytm. Wiemy, że logarytm rośnie wolniej niż dowolna dodatnia potęga \(\displaystyle{ n,}\) więc intuicja jest taka, że dzielenie przez potęgę logarytmu nie osłabi \(\displaystyle{ n^3}\) o żadną dodatnią potęgę \(\displaystyle{ n.}\) Czyli

\(\displaystyle{ n^2 \sqrt{n} = \frac{n^3}{\sqrt{n}} \prec \frac{n^3}{( \log_2 n )^7} \approx \frac{n^3}{7 ( \log_2 n )^7}.}\)