La determinación de una recurrencia BigO

Question

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

¿Cómo puedo determinar BigO de esto rápidamente?

Answer 1

El uso repetido backsubstitution y encontrar el patrón. Un ejemplo aquí .

Answer 2

No estoy del todo seguro de lo que es dn, pero suponiendo que se refiere a una constante multiplicada por n:

Según Wolfram Alpha , la solución de la ecuación de recurrencia para:

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

es:

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

lo que haría que este O(n).

Answer 3

Bueno, la parte recurrencia de la relación es de (n / 2) parte de la T, que es, en efecto, reducir a la mitad el valor de n cada vez.

Por lo tanto, necesitará aprox. (Log2 n) pasos para llegar a la condición de terminación, por lo tanto el coste global del algoritmo es O (log2 n). Puede ignorar la parte dn como se trata de una operación de tiempo constante para cada paso.

Tenga en cuenta que como se ha dicho, el problema no necesariamente terminará desde reducir a la mitad un valor arbitrario de n en repetidas ocasiones es poco probable que golpeó exactamente 1. sospecho que el T (n / 2) parte en realidad debería leer T (piso (n / 2)) o algo por el estilo con el fin de asegurar que este termina.

Answer 4

teorema uso de maestría ver http://en.wikipedia.org/wiki/Master_theorem

Por cierto, el comportamiento asintótico de su recurrencia es O (n), suponiendo d es positiva y suficientemente menor que n (tamaño de problema)