Complessità del fattoriale algoritmo ricorsivo

Question

Oggi in classe il mio insegnante ha scritto sulla lavagna questo ricorsivo algoritmo fattoriale:

int factorial(int n) { 
    if (n == 1) 
     return 1; 
    else 
     return n * factorial(n-1); 
} 

Ha detto che ha un costo di T(n-1) + 1.

Quindi con il metodo di iterazione ha detto che T(n-1) = T(n-2) + 2 = T(n-3) + 3 ... T(n-j) + j, quindi l'algoritmo si interrompe quando n - j = 1, quindi j = n - 1.

Successivamente, ha sostituito j in T(n-1) + 1 e ha ottenuto T(1) + n-1.

ha direttamente detto che per quella n-1 = 2 ^{(log 2 n-1)}, quindi il costo dell'algoritmo è esponenziale.

Ho davvero perso gli ultimi due passaggi. Può piacere che qualcuno me lo spieghi?

Answer 1

Iniziamo con l'analisi di questo algoritmo. Possiamo scrivere una relazione di ricorrenza per la quantità totale di lavoro svolto. Come un caso base, si esegue un'unità di lavoro quando l'algoritmo viene eseguito su un input di dimensione 1, così

T (1) = 1

Per un input di dimensione n + 1 , il tuo algoritmo fa una unità di lavoro all'interno della funzione stessa, quindi effettua una chiamata alla stessa funzione su un input di dimensione n. Pertanto

T (n + 1) = T (n) + 1

Se si espande i termini della ricorrenza, si ottiene che

• T (1) = 1
• T (2) = T (1) + 1 = 2
• T (3) = T (2) + 1 = 3
• T (4) = T (3) + 1 = 4
• ...
• T (n) = n

Quindi, in generale, questo algoritmo richiede n unità di lavoro per completare (vale a dire T (n) = n).

La prossima cosa che il tuo insegnante ha detto è che

T (n) = n = 2 ^{log n}

Questa affermazione è vera, perché 2 ^{log x} = x per qualsiasi x diverso da zero, poiché l'esponenziazione e i logaritmi sono operazioni inverse l'uno dell'altro.

Quindi la domanda è: è questo tempo polinomiale o tempo esponenziale? Lo classificherei come tempo pseudopolinomiale.Se si considera l'input x come un numero, allora il runtime è effettivamente un polinomio in x. Tuttavia, il tempo polinomiale è definito formalmente in modo tale che il tempo di esecuzione dell'algoritmo deve essere un polinomio rispetto al numero di bit utilizzati per specificare l'input del problema. Qui, il numero x può essere specificato solo in bit Θ (log x), quindi il tempo di esecuzione del 2 ^{registro x} viene considerato tecnicamente come tempo esponenziale. Ho scritto su questo come lunghezza in this earlier answer e consiglierei di esaminarlo per una spiegazione più approfondita.

Spero che questo aiuti!