•  21-09-2019
  •  | 
  •  

Domanda

Perché la relazione di ricorrenza di un algoritmo ricorsivo fattoriale questo? 

T(n)=1 for n=0
T(n)=1+T(n-1) for n>0

Perché non è questo? 

T(n)=1 for n=0
T(n)=n*T(n-1) for n>0

valori di n Mettendo cioè 1,2,3,4 ...... la seconda relazione ricorrente detiene (I fattoriali sono calcolate correttamente) non il primo.

È stato utile?

Soluzione

Questa domanda è molto confusa ... Lei prima formula non è fattoriale. È semplicemente T (n) = n + 1, per ogni n. Fattoriale di n è il prodotto dei primi n numeri interi positivi: fattoriale (1) = 1. fattoriale (n) = n * fattoriale (n-1). La tua seconda formula è sostanzialmente corretta.

Altri suggerimenti

appare come T (n) è il rapporto ricorrenza della Ora complessità dell'algoritmo ricorsivo fattoriale, ipotizzando costante di tempo di moltiplicazione. Forse letto male la vostra fonte?

generalmente usiamo ricorrenza rapporto per trovare la complessità temporale dell'algoritmo.

Qui, la funzione T (n) non è in realtà per il calcolo del valore di un fattoriale, ma si sta raccontando la complessità temporale dell'algoritmo fattoriale.

Questo significa per la ricerca di un fattoriale di n ci vorranno più 1 funzionamento di fattoriale di n-1 (Cioè T (n) = T (n-1) +1) e così via.

modo corretto relazione ricorrente per un algoritmo ricorsivo fattoriale è T (n) = 1 per n = 0 T (n) = 1 + T (n-1) per n> 0 Non che lei ha citato in seguito.

come ricorrenza per Torre di Hanoi è T (n) = 2T (n-1) +1 per n> 0;

I supporre che si dispone di cattiva informazione. La seconda relazione di ricorrenza si citano è quello corretto, come avete osservato. Il primo genera solo i numeri naturali.

Dove hai trovato il primo? E 'completamente sbagliato.

E 'solo andando a aggiungere 1 ogni volta che qualunque sia il valore è.

Quello che ha messo non era la ricorsione fattoriale, ma la complessità temporale di esso.
Supponendo che questo è il pseudocodice per tale ricorrenza: 

1. func factorial(n)
2.   if (n == 0)
3.      return 1
4.   return n * (factorial - 1)
  • Io parto dal presupposto che l'eliminazione coda ricorsione non è coinvolto.

Linea 2 e 3 costa un tempo costante, C1 e C2.
Linea 4 costa una costante di tempo pure. Tuttavia, chiama fattoriale (n-1) che avrà un certo tempo T (n-1). Inoltre, il tempo necessario per moltiplicare fattoriale (n-1) per n può essere ignorato ancora una T (n-1) viene utilizzato.
Tempo per l'intera funzione è solo la somma:. T (n) = c1 + c2 + T (n-1)
Questo, in notazione O-grande, si riduce a T (n) = 1 + T (n-1).

Questo è, come Diametro ha sottolineato, è un ricorsione piatta, quindi il suo tempo di funzionamento deve essere O (n). La sua complessità spazio sarà enorme però.

T (n) = T (n-1) + 1 è l'equazione di ricorrenza corretta per fattoriale di n. Questa equazione ti dà il tempo per calcolare fattoriale di n NON valore del fattoriale di n.

Per prima cosa devi trovare un funzionamento di base e per questo esempio è la moltiplicazione. Moltiplicazione avviene una volta ogni ricorsione. Così T (n) = T (n-1) +1 questo è +1 funzionamento di base (mutliplication per questo esempio) T (n-1) è chiamata successiva ricorsione.

TL; DR: La risposta alla tua domanda dipende in realtà su che sequenza la tua relazione di ricorrenza è che definisce . Cioè, se la sequenza di T n nella tua domanda rappresenta la funzione fattoriale o il costo di esercizio a tempo di calcolo della funzione fattoriale X .

La funzione fattoriale

ricorsiva defintion del fattoriale di n , f n , è:

f n = n • f n-1 per n> 0 con f < sub> 0 = 1 .

Come si può vedere, l'equazione di cui sopra è in realtà un relazione ricorrente , dal momento che è un equazione che, insieme con il termine iniziale (cioè, f 0 = 1 ), ricorsivamente definisce una sequenza (cioè la funzione fattoriale, f n ).

Modellazione del costo di esercizio a tempo di calcolare il fattoriale

Ora, stiamo andando a trovare un modello per rappresentare il costo di esercizio a tempo di calcolare il fattoriale di n . Chiamiamo T n costo di esercizio a tempo di calcolo f n .

Guardando la suddetta definizione della funzione fattoriale f n , il suo costo di esercizio tempo T n consisterà costi di gestione del tempo di calcolo f n-1 (cioè, questo costo è T n-1 ) più il costo di esercizio del tempo di eseguire la moltiplicazione tra n e f n-1 . La moltiplicazione viene raggiunto in un tempo costante. Quindi potremmo dire che T n = T n-1 + 1 .

Tuttavia, qual è il valore di T 0 ? T 0 rappresenta il costo di esercizio del tempo di calcolo f 0 . Poiché il valore di f 0 viene inizialmente conosciuto per definizione, il costo di esercizio del tempo per calcolare f 0 è effettivamente costante. Pertanto, potremmo dire che T 0 = 1 .

Infine, ciò che si ottiene è:

T n = T n-1 + 1 per n> 0 con T < sub> 0 = 1 .

Questa equazione sopra è anche un reiterazione rapporto . Tuttavia, ciò che definisce (insieme con il termine iniziale), è una sequenza che modelli il costo di esercizio del tempo di calcolo della funzione fattoriale .

X tenendo conto di come la sequenza nella vostra relazione di ricorrenza è chiamata (cioè, T n ), penso che molto probabilmente rappresenta quest'ultimo, cioè, il costo di esercizio del tempo di calcolo della funzione fattoriale .

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top