Ho il seguente elaborato:Come risolvere: T (n) = T (n - 1) + n
T(n) = T(n - 1) + n = O(n^2)
Ora quando lavoro questo fuori trovo che il limite è molto sciolto. Ho fatto qualcosa di sbagliato o è proprio così?
Pensateci in questo modo:
In ogni "iterazione" della ricorsione eseguite O (n).
Ogni iterazione ha n-1 lavoro da fare, fino a n = caso base. (Sto assumendo che il caso base sia O (n) lavoro)
Pertanto, assumendo che il caso base sia un costante indipendente da n, ci sono O (n) iterazioni della ricorsione.
Se avete n iterazioni di O (n) funzionano ciascuna, O (n) * O (n) = O (n^2).
L'analisi è corretta. Se desideri maggiori informazioni su questo modo di risolvere le ricadute, guarda su Alberi di ricorsione. Sono molto intuitivi rispetto agli altri metodi.
È necessario anche un caso base per la relazione di ricorrenza.
T(1) = c
T(n) = T(n-1) + n
Per risolvere questo, è possibile prima indovinare una soluzione e quindi dimostrare che funziona utilizzando l'induzione.
T(n) = (n + 1) * n/2 + c - 1
Prima il caso base. Quando n = 1 questo dà c come richiesto.
Per gli altri n:
T(n)
= (n + 1) * n/2 + c - 1
= ((n - 1) + 2) * n/2 + c - 1
= ((n - 1) * n/2) + (2 * n/2) + c - 1
= (n * (n - 1)/2) + c - 1) + (2 * n/2)
= T(n - 1) + n
Quindi la soluzione funziona.
Per ottenere l'ipotesi, in primo luogo, notare che il vostro rapporto ricorrenza genera il triangular numbers quando c = 1:
T(1) = 1:
*
T(2) = 3:
*
**
T(3) = 6:
*
**
***
T(4) = 10:
*
**
***
****
etc..
Intuitivamente un triangolo è circa la metà di un quadrato, e in notazione O-grande della le costanti possono essere ignorate, quindi O (n^2) è il risultato atteso.
Potresti dirmi come sei arrivato alla terza equazione nella tua risposta? Quale tecnica matematica hai applicato ad essa? –
@Tony: è una "ipotesi". In realtà è perché conosco la formula per i numeri triangolari - non l'ho davvero indovinato, lo sapevo già. Spesso è più facile "indovinare" la risposta corretta e dimostrare che è corretta invece di derivarla dai primi principi. Questa è una tecnica standard per risolvere i rapporti di ricorrenza. –
@Tony: il termine tecnico per un'ipotesi istruita è "ansatz". Vedi: http://en.wikipedia.org/wiki/Ansatz. Vi sono alcune informazioni sull'uso di un'ipotesi per risolvere una relazione di ricorrenza in Wikipedia: http://en.wikipedia.org/wiki/Recurrence_relation.Qui sono elencati anche altri possibili metodi per risolvere le relazioni di ricorrenza. –
Sembra giusto, ma dipenderà dal caso base T (1). Supponendo che tu faccia n passi per ottenere T (n) a T (0) e ogni volta che il termine n è ovunque tra 0 e n per una media di n/2 quindi n * n/2 = (n^2)/2 = O (n^2).
La soluzione è abbastanza semplice per questo. È necessario srotolare la ricorsione:
T(n) = T(n-1) + n = T(n-2) + (n - 1) + n =
= T(n-3) + (n-2) + (n-1) + n = ... =
= T(0) + 1 + 2 + ... + (n-1) + n
Hai progressione aritmetica qui e la somma è 1/2*n*(n-1). Tecnicamente qui manca la condizione al contorno, ma con qualsiasi condizione al contorno costante si vede che la ricorsione è O(n^2).
Ero troppo in gamba per tutto ciò che penso, e ho dimenticato il fatto che abbiamo a che fare con una ricorsione. Forse è per questo che non lo capisco. Per quanto sopra ho ottenuto T (n) <= 2n sarebbe corretto? –
Non ho ben capito cosa stai chiedendo, c'è molto più sopra – Rubys
@Tony: No, non è corretto. T (n) può essere maggiore di 2n per il piccolo n. –