Tschebysmasticare polynom ricorsivo

dovrei implementare un algoritmo ricorsivo:

T0(y) = 1
T1(y) = y
Tn(y) = 2yTn-1(y) - Tn-2(y) for n>1

ecco la mia implementazione:

public static int TP(int y, int n) {
    if (n == 0) {
        return 1;
    } else if (n == 1) {
        return y;
    } else {
        return 2*y*TP(y, n-1) - TP(y, n-2);
    }
}

ho implementato l’algoritmo giusto? e come posso calcolare il runtime asintotico in funzione di n.

EN From: Tschebyschew polynom recursive

More similar articles:

4 Comments

  1. yeah ho ottenuto i risultati, ma non so realmente calcolare il runtime, so che il ricorsivo di fibonacci ha runtime O (1.618 ^ n) ma come sembra con fattore di 2y
    • sì, l’implementazione sembra bene.
    • per calcolare il limite superiore sul runtime, possiamo assumere per qualsiasi n, la funzione effettua due chiamate ricorsive fino a raggiungere n = 0 or 1.
    • questo può essere visualizzato come un albero binario con i livelli n (ogni chiamata alla funzione chiamandola due volte ricorsivamente).
    • quindi la complessità di tempo per questo sarebbe O(2^n).
    • questo può essere risolto su O(n) con riproduzione.

Leave a Reply

Your email address will not be published. Required fields are marked *