Złożoność obliczeniowa algorytmu stosującego rekurencję

Odpowiedz Nowy wątek
2013-01-15 18:38
adamek_n
0

Witam jako, że są to moje początki proszę o wyrozumiałość. W programie napisałem funkcję, która umożliwia obliczenie wartości wielomianu w sposób rekurencyjny. Potrzebuje obliczyć złożoność tej części programu.

Pozostało 580 znaków

2013-01-15 18:39
adamek_n
0

float polyRec(float x, float xp, int n, vector<float> a)
{
    if(n >= a.size())
    return 0;
    return a[n] * xp + polyRec(x, xp*x, n+1, a);
}

Mógłby mi ktoś wyjaśnić na "chłopski" rozum jak się wykonuje takie obliczenia dla rekurencji? Ile wynosi taka złożoność w tym przypadku?

Pozostało 580 znaków

2013-01-15 18:51
0

Narysuj sobie drzewo wywołań funkcji http://pl.wikipedia.org/wiki/Drzewo_wywo%C5%82a%C5%84_funkcji
Dodatkowo a jest przekazywane przez wartość, przez co(o ile liczyć kopiowanie wektora) złożoność w tym przypadku jest gorsza.


I fart u die.
edytowany 1x, ostatnio: mychal, 2013-01-15 18:51

Pozostało 580 znaków

2013-01-27 22:26
0

Złożoność jest liniowa czyli O(teta)=n i to w pesymistycznym wariancie. Po prostu wykonywany jest algorytm od n do momentu gdy n>=a.size().

tak. i za każdym razem kopiowany jest n-elementowy wektor, co daje theta(n^2). - mychal 2013-01-27 22:42

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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