Buenas tardes, no me quedó muy claro por qué 2^c_max es mayor o igual a n!
Alguna idea?
Hola.
Como la respuesta del algoritmo depende exclusivamente de los resultados de las comparaciones que realiza, y cada comparación tiene dos resultados posibles (verdadero/falso), hay como máximo 2^C_max respuestas posibles distintas (2^C_max es la cantidad de secuencias binarias distintas de largo C_max). Por otra parte, si no hay ninguna hipótesis adicional sobre las posibles entradas, un algoritmo de ordenamiento correcto debe ser capaz de emitir n! respuestas distintas. Por ejemplo, cada una de las n! entradas distintas que podemos formar permutando n elementos todos distintos entre sí admite una única forma de ordenarla correctamente, que es distinta a la de todas las demás. Por lo tanto el algoritmo debe ser capaz de generar n! respuestas distintas, entendiendo como respuesta una permutación de la entrada que hace que dicha entrada quede ordenada.
Si 2^C_max fuera menor que n!, habría al menos un par de esas entradas para las cuales la secuencia de resultados de comparaciones que hace el algoritmo sería exactamente la misma, por lo cual el algoritmo hace exactamente lo mismo, emitiendo la misma respuesta en ambos casos, y necesariamente alguna de esas dos respuestas es equivocada.
Saludos,
Álvaro
Como la respuesta del algoritmo depende exclusivamente de los resultados de las comparaciones que realiza, y cada comparación tiene dos resultados posibles (verdadero/falso), hay como máximo 2^C_max respuestas posibles distintas (2^C_max es la cantidad de secuencias binarias distintas de largo C_max). Por otra parte, si no hay ninguna hipótesis adicional sobre las posibles entradas, un algoritmo de ordenamiento correcto debe ser capaz de emitir n! respuestas distintas. Por ejemplo, cada una de las n! entradas distintas que podemos formar permutando n elementos todos distintos entre sí admite una única forma de ordenarla correctamente, que es distinta a la de todas las demás. Por lo tanto el algoritmo debe ser capaz de generar n! respuestas distintas, entendiendo como respuesta una permutación de la entrada que hace que dicha entrada quede ordenada.
Si 2^C_max fuera menor que n!, habría al menos un par de esas entradas para las cuales la secuencia de resultados de comparaciones que hace el algoritmo sería exactamente la misma, por lo cual el algoritmo hace exactamente lo mismo, emitiendo la misma respuesta en ambos casos, y necesariamente alguna de esas dos respuestas es equivocada.
Saludos,
Álvaro