obliczenie asymptotycznego stopienia złożoności

0

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

\sum_{k=0}^{n} k \sqrt{k}
\frac{n<sup>3}{7*(log _{2} (n))</sup>7}
\frac{n^2+2}{log _{2} (n)}

ćwiczenie jest ze strony http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1/%C4%86wiczenia_9:_Asymptotyka

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

1

Nie do końca rozumiem pytanie. Nie musisz tu przecież obliczać tego tak całkiem, wystarczy czy zrobić oszacownie, na oko wystarczy duże O, więc tylko górne ograniczenie.
Mógłbyś sie pokusić po prostu o analizę przebiegu zmienności tych funkcji jeśli bardzo lubisz analizę matematyczną :)

Pierwsza funkcja to jest zwykła suma której największy wyraz to nsqrt(n) więc siłą rzeczy jest ona rzędu O(nsqrt(n)) czyli O(n3/2)
Druga funkcja będzie oczywiście rzędu O(n3/log2(n)7) a trzecia O(n2/log2(n)). Jeśli te dwie funkcje porównasz (i podzielisz stronami) to wychodzi z tego porównanie O(n/log2(n)6) i O(1) czyli pytanie brzmi: jaka jest granica przy n dążącym do nieskończoności z n/log2(n)6, czy jest w 0 czy w nieskończoności. Jeśli jest w 0 to znaczy że funkcja 2 rośnie wolniej niż funkcja 3, jeśli w nieskończoności to odwrotnie. Analogiczne pytanie nasuwa się przy porównaniu dowolnej innej pary.

0
Shalom napisał(a):

Nie do końca rozumiem pytanie. Nie musisz tu przecież obliczać tego tak całkiem, wystarczy czy zrobić oszacownie, na oko wystarczy duże O, więc tylko górne ograniczenie.
Mógłbyś sie pokusić po prostu o analizę przebiegu zmienności tych funkcji jeśli bardzo lubisz analizę matematyczną :)

Pierwsz funkcja to jest zwykła suma której największy wyraz to nsqrt(n) więc siłą rzeczy jest ona rzędu O(nsqrt(n)) czyli O(n3/2)
Druga funkcja będzie oczywiście rzędu O(n3/log2(n)7) a trzecia O(n2/log2(n)). Jeśli te dwie funkcje porównasz (i podzielisz stronami) to wychodzi z tego porównanie O(n/log2(n)6) i O(1) czyli pytanie brzmi: jaka jest granica przy n dążącym do nieskończoności z n/log2(n)6, czy jest w 0 czy w nieskończoności. Jeśli jest w 0 to znaczy że funkcja 2 rośnie wolniej niż funkcja 3, jeśli w nieskończoności to odwrotnie. Analogiczne pytanie nasuwa się przy porównaniu dowolnej innej pary.

Mam jeszcze takie pytanie, że tam było jeszcze (sqrt(n)+1)<sup>3=O(n<em>sqrt(n)) i wtedy mam problem że\sum_{k=0}</sup>{n} k \sqrt{k}=O(n</em>sqrt(n)) więc czy dokładniejszym oszacowaniem tego jest O(n*sqrt(n))+O(1)?
P.S. Jeszcze nie umiem liczyć dobrze całek więc innego pomysłu nie mam

1

@masterkwi a jak policzysz sobie granicę z różnicy tych funkcji? :) Będzie od razu wiadomo która rośnie szybciej. I nie wiem co mają do tego całki.

0
Shalom napisał(a):

Pierwsz funkcja to jest zwykła suma której największy wyraz to nsqrt(n) więc siłą rzeczy jest ona rzędu O(nsqrt(n)) czyli O(n3/2)

No niespecjalnie. A jakbyś miał sumę \sum_{i=0}^{n} 1, to będzie to miało złożoność stałą O(1)?

0

aaa jakies zaćmienie miałem chyba :D oczywiście to jest bzdura co tam napisałem, trzeba to sobie zsumować ;]

1 użytkowników online, w tym zalogowanych: 0, gości: 1