Coreman y col. explique en 5.3, y traeré la versión corta:
Para el problema de contratación, el análisis probabilístico nos permite diferenciar diferentes entradas, como los conjuntos de candidatos peores a mejores: (1,2,3,4,5….) Y viceversa (10,9,8….). Esto dará como resultado costos radicalmente diferentes, ya que los costos de contratación son los más altos (ver 5.1 para revisión). Estos dos casos representan distribuciones diferentes. Para este Alg. el peor tiempo de ejecución siempre sería lg (n), por lo tanto, el alg. Es determinista .
En el caso de un algoritmo aleatorio , el algoritmo clasificará a los candidatos de tal manera que garantice una distribución específica . Eso significa que ” ninguna entrada en particular provoca su peor comportamiento. “Eso también significa que la primera línea en dicho algoritmo estará permutando la entrada. Como la permutación ocurre al azar, todas las distribuciones son igualmente probables.
Khan Academy siempre es un buen lugar para comenzar:
- Cómo encontrar la subcadena común más larga de tres o más cadenas usando una matriz de sufijos
- ¿Qué algoritmos se usan en los sistemas de recomendación?
- ¿Ha cambiado recientemente el algoritmo de Quora?
- Teoría de conjuntos: ¿un subconjunto es un tipo de intersección?
- ¿Es asintóticamente más rápido aplicar Dijkstra de ambos vértices de origen y destino simultáneamente?
Babero – Basado en Introducción a Algoritmos, Tercera Edición
