szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 17 kwi 2011, o 18:11 
Użytkownik

Posty: 35
Lokalizacja: Siedlce
Oblicz złożoność algorytmu:

T(1) = 0\\ T(n) = O(n ^{3} ) + n \cdot T(n-1)
Góra
Mężczyzna Offline
PostNapisane: 17 kwi 2011, o 20:26 
Użytkownik

Posty: 16
Lokalizacja: Gliwice
Skorzystamy ze sposobu czynnika sumacyjnego:
a_{n} = 1 \\
 b_{n} = n \\
 c_{n} = O(n ^{3} ) \\
 \\
Niestety nie możemy wprost skorzystać ze wzoru jakim oblicza się T(n), ponieważ n zaczyna się od 1, a nie od 0. Jednak ten problem wymaga łatwej korekty, poprostu do wszystkich indeksów dodajemy jedynke, zatem:
s_{n} =  \frac{a_{2}*a_{3}*...*a_{n-1}}{b_{3}*b_{4}*...*b_{n}} =  \frac{1}{\frac{n!}{2}} \\
 b_{2} = 2\\
 s_{2} = 1\\
 K = s_{n}*a_{n}

T(n) =  \frac{1}{K} * (b_{2}*s_{2}*T(1) +  \sum_{k=2}^{n}(O(n ^{3})*s_{k}))

No a dalej całe zadanie opiera się na policzeniu tej sumy, powodzenia!

PS - nie jestem pewny co do tego O(n ^{3}) czy tą n-ke traktować jak zmienna czy jako oznaczenie złożoności do potęgi 3-ciej.
Góra
Mężczyzna Offline
PostNapisane: 21 kwi 2011, o 11:01 
Gość Specjalny

Posty: 2628
Lokalizacja: Warszawa
Rozpiszmy ten drugi warunek
T(n)=\mathcal {O} (n^3)+n T(n-1)=\mathcal{O}\left( n^3 \right) + n \mathcal{O}\left( (n-1)^3 \right)+n(n-1)T(n-2)=\mathcal{O}\left( n^3 \right) + n \mathcal{O}\left( (n-1)^3 \right)+n(n-1) \mathcal{O}\left( (n-2)^3 \right)+n(n-1)(n-2)T(n-3) = \ldots =n! T(1)+  \sum_{k=1}^{n} \frac{n!}{k!} \mathcal{O}\left( k^3 \right) = \sum_{k=1}^{n} \frac{n!}{k!} \mathcal{O}\left( k^3 \right)

Teraz oczywiście
C_1 n! \le \sum_{k=1}^{n} \frac{n!}{k!} \mathcal{O}\left( k^3 \right) \le C_2 n! \sum_{k=1}^{n} \frac{ k^3 }{k!} \le C_2 n! \cdot n \le C_2 (n+1)!

Zatem jest T(n)=\mathcal( (n+1)! )

Chyba jakoś tak, ale jak coś to poprawcie.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Taka funkcja rekurencyjna  dpiotrow  2
 Złożoność obliczeniowa funkcji obliczającej  kasia123456  0
 Złożoność algorytmu - zadanie 3  Matm  6
 [Teoria złożoności] Złożoność w sensie notacji O()  palcedavosa12  0
 Złożoność DFS'a i BFS'a  daniel285  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl