Prob Algs en clase

 

Un determinístico no se desvía, no se cicla, no hay división por 0, etc.

 

Si estas cosas pasan en el probabilístico, se reinicia hoping que no pase eso. (reset).

Aunque el hardware falle el algoritmo no se equivoca.

 

Monte Carlo:

Dan la respuesta correcta con una probabilidad alta. Pero se pueden equivocar. No puede saber si es correcto o no el resultado que obtuvo. 

 

 

Las Vegas:

 

Se sabe si se falló o se obtuvo la solución. Cuando falla se vuelve a llamar el algoritmo hasta encontrarlo. 

 

 

Complejidad:

Se usa el tiempo esperado, sobre las instancias, tiempo medio que toma resolver esa instancia una y otra vez. 

Tiempo esperado en el peor de los casos: el tiempo que toma la instancia que toma más tiempo, esto sin contar que tome las peores decisiones, sino tomando la peor instancia y ejecutandola una y otra vez.