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

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.

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?

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.

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().

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