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
[Teoria złożoności] Asymptotyczny stopień złożoności
-
- Użytkownik
- Posty: 65
- Rejestracja: 18 maja 2014, o 14:09
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 12 razy
[Teoria złożoności] Asymptotyczny stopień złożoności
Ostatnio zmieniony 6 lip 2016, o 14:44 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 5974
- Rejestracja: 28 lut 2010, o 19:45
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 15 razy
- Pomógł: 1251 razy
[Teoria złożoności] Asymptotyczny stopień złożoności
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.
\(\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
- Moderator
- Posty: 10225
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
[Teoria złożoności] Asymptotyczny stopień złożoności
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}.}\)
\(\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}.}\)