Questa soluzione può essere facilmente trasformata in molto più semplice:

int res = 1;
for(int i = 1; i <= n; ++i) {
    res *= i;
}

Considerando che la moltiplicazione è O(1) (se si utilizza la moltiplicazione di Karatsuba , è O(m^1.585) , dove m è la lunghezza di un numero) il risultato è O(n) per questa funzione.

Ok, supponiamo che la moltiplicazione richieda temposuggeritodam0nhawk.

Dobbiamo definire un'equazione tempo ricorsivo:

Serisolviquestaequazione,otterrai:

Questo è fondamentalmente:

dovekèn-1equindi:

Ma se si assume che la moltiplicazione richieda tempo costante, O (n) è l'approssimazione di runtime corretta.

Mi dispiace per aver rianimato una vecchia domanda, ma penso che qui possa essere commesso un errore che viene ripetuto più e più volte.

Per quanto ne so, la complessità computazionale è definita sulla dimensione di una codifica efficiente dell'input ( n ).

Dato un numero di input m per factorial, è vero che l'algoritmo richiede moltiplicazioni m . Ma questo non è di ordine lineare (cioè lo stesso ordine della dimensione dell'ingresso codificato), perché una codifica efficiente di un numero m è di dimensione n := log m

Ciò significa che la complessità del tempo è ESPONIBILE esponenziale ( m = 2^n moltiplicazioni) nella dimensione di (una codifica efficiente di) l'input!

m sono solo lineari nell'input se scegli una codifica unaria dell'input, che non è una scelta "efficiente".

Attivato "Efficient encodings"

Poiché l'utente SSH ha chiesto, vorrei approfondire la nozione di "codifiche efficienti".

La chiave per comprenderlo è capire che la complessità asintotica di un algoritmo è definita in termini di "quanto velocemente cresce il tempo di calcolo, rispetto a quanto velocemente cresce l'input ".

Di solito la dimensione dell'input è intuitiva: un elenco di n elementi ha taglia n . Ma a volte può farti inciampare, come nell'esempio su cui si focalizza questo thread. Questo è il motivo per cui la definizione di complessità computazionale indica esplicitamente "codifica efficiente": per evitare di commettere due possibili errori:

1: dimenticando che hai bisogno di codificare i tuoi input usando un alfabeto finito

Nell'esempio fattoriale potresti commettere l'errore di pensare che la dimensione dell'input non cresca per numeri più grandi, dal momento che hai sempre a che fare con "un numero" . Questo non è valido, perché non ha senso alimentare "un numero" con una macchina di turing (è necessario un alfabeto di dimensioni infinite). Devi codificare il numero usando un alfabeto finito e questa rappresentazione di un numero aumenterà quando il numero n diventerà più grande.

2: scelta di una inefficiente codifica

Poiché la complessità computazionale è definita in relazione alla dimensione di input codificata, potremmo manipolare la complessità scegliendo una codifica molto inefficace.

Ad esempio: diciamo che codificheremmo un elenco di n elementi in modo molto inefficiente usando% token di n^2 sul nastro di input della macchina; ora all'improvviso tutti gli algoritmi che utilizzano n^2 passaggi computazionali per gli elenchi di dimensioni n sono lineari nella dimensione di input codificata! Questo non ha senso del discorso. Quindi la nostra codifica deve essere efficiente affinché la nostra analisi abbia successo.

Un altro esempio è ascoltare la tua intuizione e pensare che il numero 4 sia due volte più grande del numero 2. Questo non è il caso, perché possiamo codificare in modo efficiente il numero 2 usando 2 bit e il numero 4 usando solo 3 bit.

Trappola potenziale: crescita rispetto alla dimensione di input codificato assoluto.

Ricorda che siamo non interessati alla dimensione assoluta ma al tasso di crescita dell'ingresso codificato: una lista di 2 * n interi è ancora il doppio della dimensione di un elenco di n elementi.

Equazione di ricorrenza:

           | e                if n = 1
T(n) =     |
           | T(n - 1) + d     if n > 1

f(n) = d so is a 0-degree polynomial, n^0

T(n) ∈ Θ(n^0+1) = Θ(n)

Metodo per Chip & Conquer

Il problema della dimensione n è ridotto in un sottoprocesso di dimensione n-c.

T(n) = T(n - c) + f(n)

Se c > 0 (il fattore di cippatura) e f (n) è il costo non ricorsivo (per creare sottoproblemi e / o combinare con soluzioni di altri sottoproblemi) allora T (n) può essere limitato asintoticamente come segue:

• Se f (n) è un polinomio n^α , quindi T(n) ∈ Θ(n^(α+1))
• Se f (n) è lg n , quindi T(n) ∈ Θ(n lg n)