Złożoność algorytmu z dwoma wywołaniami rekursywnymi

Question

Mam dziwny algorytm niż jest nazywany rekurencyjnie 2 razy. Jest

W pewien sposób muszę znaleźć złożoność tego algorytmu. Starałem się znaleźć go za pomocą wielomianu charakterystycznego powyższego równania, ale system wynik jest zbyt trudne do rozwiązania, więc zastanawiałem się czy jest jakaś inna droga prosto ..

Answer 1

założeniach:

1 : n >= 0

2: Θ(3n+1) = 3n + 1

Złożoność:

O(2^n * (3n - 2)); 

Rozumowanie:

int alg(int n) 
    loop body = Θ(3n+1)// for every n you have O(3n+1) 
    alg(n-1); 
    alg(n-2) 

Zakładając ALG nie zrealizuje dla n < 1, masz następujące powtórzeń:

Etap N:

3 * n + 1 
alg(n - 1) => 3 * (n - 1) + 1 
alg(n - 2) => 3 * (n - 2) + 1 

teraz ty zasadniczo mają podział. Musisz wyobrazić sobie drzewo liczb z N jako rodzicem, a n-1 i n-2 jako dziećmi.

         n 
       n-1         n-2 
      n - 2  n - 3      n - 3  n - 4 
    n - 3 n - 4 n - 4 n - 5    n - 4 n - 5 n - 5 n - 6 
    n-4 n-5 | n-5 n-6 |n-5 n-6 |n-6 n-7 n-5 n-6 n-6 n-7 n-6 n-6| n-6 n-8 

To oczywiste, że istnieje tutaj wzór powtarzania. Dla każdej pary, z wyjątkiem dwóch pierwszych i dwóch ostatnich, (n - 1, n - 2) and (n-2, n-3), występuje złożoność .

Patrzę na liczbę powtórzeń pary (n - k, n - k - 1). Więc teraz dla każdego k od 0 to n mam:

(3k + 1) * (2^(k - 1)) iterations. 

Jeśli to podsumować od 1 do n należy uzyskać pożądany rezultat. Będę rozwinąć wyrażenie:

(3k + 1) * (2^(k - 1)) = 3k * 2^(k - 1) + 2^(k - 1) 

Aktualizacja

1 + 2 + 2^2 + 2^3 + ... + 2^n = 2^(n + 1) - 1 

W twoim przypadku, to nakręca samopoczucie:

2^n - 1 

oparciu o formułę sumy i k = 0, n . Teraz pierwszy:

3k * 2^(k - 1) 

Jest to równa 3 suma od k = 0, n of k * 2^(k - 1). Ta suma może zostać określona poprzez przełączenie na funkcje polinomialne, całkowanie, kontraktowanie przy użyciu formuły 1 + a^2 + a^3 + ... + a^n, a następnie ponowne różnicowanie w celu uzyskania wyniku, którym jest (n - 1) * 2^n + 1.

Więc trzeba:

2^n - 1 + 3 * (n - 1) * 2^n + 1 

Które zamówienia jest:

2^n * (3n - 2); 

Answer 2

Złożoność: alg(n) = Θ(φ^n) gdzie φ = Golden Ratio = (1 + sqrt(5))/2

Nie mogę formalnie udowodnić najpierw, ale z nocną pracą, znajduję moją brakującą część - Metoda podstawienia z odjęcie niższego rzędu termin. Przepraszam za mój zły wyraz oceny (∵ słaby angielski).

---

Niech loop body = Θ(3n+1) ≦ tn

Załóżmy (przypuszczenie), że cφ^n ≦ alg(n) ≦ dφ^n - 2tn dla n (n ≧ 4)

Rozważmy alg(n+1):

 
Θ(n) + alg(n) + alg(n-1) ≦ alg(n+1) ≦ Θ(n) + alg(n)  + alg(n-1) 
    c * φ^n + c * φ^(n-1) ≦ alg(n+1) ≦ tn + dφ^n - 2tn + dφ^(n-1) - 2t(n-1) 
       c * φ^(n+1) ≦ alg(n+1) ≦ tn + d * φ^(n+1) - 4tn + 2 
       c * φ^(n+1) ≦ alg(n+1) ≦ d * φ^(n+1) - 3tn + 2 
       c * φ^(n+1) ≦ alg(n+1) ≦ d * φ^(n+1) - 2t(n+1) (∵ n ≧ 4) 

Tak to jest poprawne dla n + 1. Dzięki indukcji matematycznej wiemy, że jest poprawna dla wszystkich n.

Więc cφ^n ≦ alg(n) ≦ dφ^n - 2tn, a następnie alg(n) = Θ(φ^n).

Answer 3

Ciało funkcji zajmuje czas Θ(n). Funkcja jest wywoływana dwukrotnie rekursywnie.

dla danej funkcji złożoność jest,

 T(n) = T(n-1) + T(n-2) + cn  ----- 1 
    T(n-1) = T(n-2) + T(n-3) + c(n-1) ----- 2 

1-2 -> T(n) = 2T(n-1) - T(n-3) + c  ----- 3 

3 --> T(n-1) = 2T(n-2) + T(n-4) + c  ----- 4 

3-4 -> T(n) = 3T(n-1) - 2T(n-2) - T(n-3) - T(n-4) ----- 5 

Niech g(n) = 3g(n-1)

ma na możemy przybliżeniu T(n) = O(g(n))

g (n) jest Θ (3 ⁿ)

There for T (n) = O (3 ⁿ)

Answer 4

johnchen902 jest poprawne:

alg(n)=Θ(φ^n) gdzie φ = Golden ratio = (1 + sqrt(5))/2

ale jego argument jest zbyt ręcznie zawijania, tak zróbmy to surowo. Jego pierwotny argument był niekompletny, dlatego dodałem moje, ale teraz he has completed the argument.

---

loop body = Θ(3n+1) 

Oznaczmy koszty ciała pętli dla argumentu n z g(n).Następnie g(n) ∈ Θ(n) od Θ(n) = Θ(3n+1).

Ponadto, niech T(n) będzie całkowity koszt alg(n) dla n >= 0. Następnie dla n >= 2 mamy nawrót

T(n) = T(n-1) + T(n-2) + g(n) 

Dla n >= 3 możemy wstawić nawrotom zastosowany do T(n-1) do tego,

T(n) = 2*T(n-2) + T(n-3) + g(n) + g(n-1) 

i n > 3, możemy kontynuować, stosując nawrót do T(n-2). W przypadku dostatecznie dużej n, dlatego mają

T(n) = 3*T(n-3) + 2*T(n-4) + g(n) + g(n-1) + 2*g(n-2) 
    = 5*T(n-4) + 3*T(n-5) + g(n) + g(n-1) + 2*g(n-2) + 3*g(n-3) 
    ... 
             k-1 
    = F(k)*T(n+1-k) + F(k-1)*T(n-k) + ∑ F(j)*g(n+1-j) 
             j=1 

           n-1 
    = F(n)*T(1) + F(n-1)*T(0) + ∑ F(j)*g(n+1-j) 
           j=1 

z Fibonacciego F(n) [F(0) = 0, F(1) = F(2) = 1].

i T(1) to niektóre stałe, więc pierwsza część to oczywiście Θ(F(n)). Pozostaje zbadać kwotę.

Od g(n) ∈ Θ(n), musimy tylko do zbadania

 n-1 
A(n) = ∑ F(j)*(n+1-j) 
     j=1 

Teraz

    n-1 
A(n+1) - A(n) = ∑ F(j) + (((n+1)+1) - ((n+1)-1))*F((n+1)-1) 
       j=1 

       n-1 
       = ∑ F(j) + 2*F(n) 
       j=1 

       = F(n+1) - 1 + 2*F(n) 
       = F(n+2) + F(n) - 1 

Reasumując, że wychodząc z A(2) = 2 = F(5) + F(3) - 5 otrzymujemy

A(n) = F(n+3) + F(n+1) - (n+3) 

a zatem z

c*n <= g(n) <= d*n 

szacunek

F(n)*T(1) + F(n-1)*T(0) + c*A(n) <= T(n) <= F(n)*T(1) + F(n-1)*T(0) + d*A(n) 

dla n >= 2. Od F(n+1) <= A(n) < F(n+4) wszystkie terminy w zależności od n w lewej i prawej części nierówności to Θ(φ^n), q.e.d.