Determinazione Bigo di reiterazione

Question

T (1) = c    
T (n) = T (n/2) + dn

Come faccio a determinare Bigo di questa fretta?

Answer 1

L'uso ripetuto backsubstitution e trovare il modello. Un esempio qui .

Answer 2

Non sono del tutto sicuro di quello che è dn, ma supponendo che si intende una costante moltiplicata per n:

Secondo Wolfram Alpha , la soluzione dell'equazione ricorrenza per:

f(n) = f(n / 2) + cn

è:

f(n) = 2c(n - 1) + c1

che renderebbe questo O(n).

Answer 3

Bene, la parte ricorrenza della relazione è T (n / 2) parte, che è in effetti dimezzare il valore di n ogni volta.

In questo modo si avrà bisogno di circa. (Log2 n) passi per raggiungere la condizione di terminazione, quindi il costo complessivo dell'algoritmo è O (log2 n). È possibile ignorare la parte dn come è un'operazione costante di tempo per ogni passo.

Si noti che come detto, il problema non è necessariamente terminare in quanto dimezzare un valore arbitrario di n volte è improbabile per colpire esattamente 1. Ho il sospetto che il T (n / 2) parte dovrebbe effettivamente letto T (piano (n / 2)) o qualcosa di simile, al fine di garantire che questo termina.

Answer 4

Il teorema uso del padrone vedi http://en.wikipedia.org/wiki/Master_theorem

A proposito, il comportamento asintotico della recidiva è O (n) dove D è positivo e sufficientemente minore di n (dimensione del problema)