Trovare relazioni di ricorrenza di un algoritmo

Question

sto leggendo il mio libro di testo algoritmi, e sto leggendo di relazioni di ricorrenza e di trovare gli algoritmi di grande complessità O. Corro attraverso questa linea

"In the case of the merge-sort algorithm, we get the recurrence equation:

    t(n) = b                  if n < 2

         = 2t(n/2) +bn        if n >= 2

for b > 0

la mia risposta è stata "come il diavolo ha fatto sappiamo che?!?!"

Quindi, mi chiedo se non v'è un approccio sistematico, o semplicemente un modo logico di ottenere questi relazioni di ricorrenza dagli algoritmi

qualcuno può spiegare dove il b e le due 2 della provengono?

Answer 1

L'algoritmo di merge sort possono essere riassunti come:

mergesort (array A) {
   mergesort (first half of A);
   mergesort (second half of A);
   merge the two halves and return;
}

C'è un O (N) algoritmo per fondere due array di lunghezza N, cioè la sua complessità è bN per una costante b > 0.

Supponendo che la complessità di mergesort è T (N). Dal momento che la metà di N è N / 2, vediamo che:

mergesort (array A) {                    T(N)    =
   mergesort (first half of A);          T(N/2)  +
   mergesort (second half of A);         T(N/2)  +
   merge the two halves and return;       bN
}

che spiega la N = 2 caso.

Il N <2 caso (il caso base in cui si arresta la ricorsione) è banale.

Answer 2

Bene, questa affermazione è (presumibilmente) la conclusione di una discussione, o per lo meno una dichiarazione, l'algoritmo in questione. Senza i dettagli posso solo fatte ipotesi plausibili, che sarebbe andato in questo modo:

• la prima cosa che l'algoritmo non è controllare se è stato chiesto di elaborare 0 o 1 elementi. Se questo è vero, restituisce immediatamente. Così, poi n < 2, v'è un costo fisso - lo chiamano b
• Per n >= 2, l'algoritmo divide il suo ingresso in due pezzi, ciascuno di dimensione n/2, e si invoca su ogni pezzo. Ogni tale invocazione avrà un costo di t(n/2), e ci sono due tali invocazioni
• Non v'è quindi un costo aggiuntivo per unire i due pezzi di nuovo insieme - questo costo sarà proporzionale alla n - chiamata è b volte n

L'unica piccola stranezza è che non è del tutto evidente il motivo per cui i due fattori costanti che emergono dovrebbero essere gli stessi -. Ma parte del punto di analisi O-grande è che i fattori costanti alla fine non contano

Answer 3

T(n) = c if n < d
     = A*T(n/b) + f(n)

dove d> = 1 e molte sottoproblemi e sottoproblemi sono al massimo dimensione n / b. f (n) è il tempo supplementare totale necessario per dividere il problema in sottoproblemi e unire le soluzioni sottoproblemi in una soluzione al problema intero.

questo è per algoritmi divide et impera.

Mi chiedo perché ci sono 2 sottoproblemi in merge sort?