złożoność obliczeniowa algorytmów

[sarenka]

Witam , mam prośbę o pomoc przy rozwiązaniu poniższych zadań . Dodam tylko że zadania są z zakresu złożoności obl. algorytmów , przeglądam książki ale nie wiem jak się za to zabrać

--1-----
dany jest algorytm rekurencyjny :
a(n)
1 if n=0 then return 6
2 if n =1 then return 21
3 if n =2 then return 11
4 if n >2 then return 3 *a(n-1)+a(n-3)+10 * n+2

pokaż że dla całkowitego n>= 0 zachodzi a(n) =1 (mod5)
--2-----

Oszacuj nast. Sumy:
\(\displaystyle{ \sum_{k=1}^{n}}\) \(\displaystyle{ \frac{4}{3k-2}}\)
\(\displaystyle{ \sum_{k=1}^{n}}\) \(\displaystyle{ \sqrt{k}}\)


--3-----
Znajdź możliwie najlepsze oszacowania:
\(\displaystyle{ {2n \choose n}}\) = 0(?)
\(\displaystyle{ { n*n \choose n}}\) = 0(?)

-- 4 ----
zliczaj (n)
1 r=0
2 for i=1 to n-1 do
3 for j=i+1 to n do
4 for k=1 to j do
5 r=r+1
6 return r

Jaka wart. Zostanie zwrócona przez powyższa funk.? Wyraź odp. Jako funk. Zmiennej n.[/color]
---------------------

mile widziana byłaby łopatologia dzięki z góry za poświęcony czas ...

[Dumel]

3. mozesz zrobic ze wzoru Strirlinga
4. liczba operacji:
\(\displaystyle{ \sum_{i=1}^{n-1}((i+1)+(i+2)+...+n)= \sum_{i=1}^{n-1} \frac{(n-i)(n+i+1)}{2}= \sum_{i=1}^{n-1} \frac{1}{2}(n^2+n-i^2-i)= \frac{1}{2}((n-1)n^2+(n-1)n- \frac{(n-1)n(2n-1)}{6}- \frac{n(n-1)}{2} )}\)
nie chce mi sie tego redukowac ale dalej to juz sobie poradzisz, wyjdzie pewnie \(\displaystyle{ O(n^3)}\)

[sarenka]

serdeczne dzięki , a jakieś wskazówki do 1 i 2 ? mógłby mi ktoś podpowiedzieć ?

[Dumel]

zad.2
najpierw oszacowanie od dołu (nierownosc miedzy srednia arytmetyczna i geometryczna i wzor Stirlinga)
\(\displaystyle{ \frac{\sum_{k=1}^{n} \sqrt{k} }{n}> \sqrt[2n]{n!}> \sqrt{ \frac{n}{e} }}\)
a teraz od góry (nierownosc miedzy srednia kwadratowa i srednia arytmetyczna):
\(\displaystyle{ \frac{\sum_{k=1}^{n} \sqrt{k} }{n}< \sqrt{\frac{\sum_{k=1}^{n} k }{n}}= \sqrt{ \frac{n+1}{2} }}\)

czyli
\(\displaystyle{ \frac{n^{1,5}}{e}< \sum_{k=1}^{n} \sqrt{k}< \frac{n \sqrt{n+1} }{ \sqrt{2} }}\)
widzimy ze to oszacowanie jest asymptotycznie dokładne

[bastek1988]

Witam,
chciałbym podbić temat z pytaniem jak zrobić zadanie nr 1. Pomyślałem, że trzeba po prostu wyliczyć wzór ogólny tej rekurencji. I tu sie pojawia problem. Jaką metoda należy to zrobić? Wyznaczyć równanie charakterystyczne raczej nie bo nie bardzo sie da wyliczyć te równanie charakterystyczne a poza tym ten człon 10n+2. A więc trzeba zrobić to z funkcji tworzących?
Wziąłem sie za to i nie bardzo wiem co potem zrobić z ty ostatnim członem 10n+2 \(\displaystyle{ \sum_{0}^{ \infty } (10n+2)x^{n}}\)
W ogóle czy dobrze rozumuje, żę tak to ma być czy może w ogóle o co innego chodzi w tym zadaniu.
Z góry dziekuje.