Digamos que tienes una baraja aleatoria de $N$ diferentes tarjetas. Un $M$ -acción ( $M\le N$ ) se define de la siguiente manera: se mira la parte superior $M$ cartas de la baraja, pon todas las que elijas en la parte superior del mazo y el resto en la parte inferior, cada vez en el orden que elijas. Cuántas $M$ -acciones que se necesitan para organizar un $N$ -mazo de cartas en un orden determinado?
Respuesta
¿Demasiados anuncios?
Llamemos a la operación de mirar hacia arriba $M$ cartas y colocándolas en la parte superior y/o inferior del mazo en un orden arbitrario escudriñar . Hay $N!$ diferentes estados en los que el mazo puede estar inicialmente, y cada iteración de scry M presenta $(M+1)!$ opciones de dónde colocar las tarjetas. Así que un límite inferior simple es que, en el peor de los casos, debe tomar $\lceil{\log(N!)/\log((M+1)!)}\rceil$ iteraciones para ordenar el mazo. Esto es conservador, como se ve al considerar el $M=1$ caso, en el que la tarea puede no ser ni siquiera realizable.
Un mejor límite inferior se obtiene imaginando las cartas en un círculo, con un puntero entre las cartas inferiores y superiores. Entonces la operación scry M se convierte en: reordenar el $M$ tarjetas en el sentido de las agujas del reloj desde el puntero, en su lugar, y luego mueva el puntero hacia arriba para $M$ lugares en el sentido de las agujas del reloj. Para colocar las cartas en el orden correcto, ignorando la posición del puntero, debe tomar $\lceil{\log((N-1)!)/\log(M!)}\rceil$ operaciones en el peor de los casos.
Por otra parte, no puede tomar más de $N^2/(M-1)$ iteraciones, como demuestra el siguiente algoritmo. Supongamos, sin pérdida de generalidad, que el orden objetivo es $\{1,2,...N\}$ . Para $i=1,2,...N$ : mueva el puntero en el sentido de las agujas del reloj por $M$ posiciones por iteración hasta que la tarjeta $i$ está en la ventana, entonces mueve la tarjeta $i$ y el puntero en el sentido de las agujas del reloj por $M-1$ posiciones por iteración hasta que el $i$ -en la ventana, entonces deposita la tarjeta $i$ en el $i$ -posición e incremento $i$ . Esto requiere como máximo $N/(M-1)$ iteraciones por tarjeta correctamente colocada. Esto puede mejorarse llevando a cabo la siguiente $k$ tarjetas en lugar de sólo una (reduciendo la distancia que el puntero puede moverse por iteración a $M-k$ ). Con esta variación, se necesita como máximo $N/(M-k)$ iteraciones por $k$ tarjetas correctamente colocadas, para un recuento total de $N^2/(k(M-k))$ iteraciones, que se minimiza en $4N^2/M^2$ tomando $k=M/2$ .
Debido al "alcance" finito de la operación, conjeturo que la complejidad real es $\Theta(N^2)$ es decir, que este límite superior es asintóticamente ajustado, y que se alcanza cuando el mazo se baraja al revés de su orden objetivo. Estoy menos seguro de la dependencia exacta de $M$ .
Actualización: Para $M=2$ y $2\le N\le10$ el número máximo de operaciones necesarias es $1,1,3,5,7,11,14,19,23.$ Esto se ajusta razonablemente bien a $\alpha N^2$ , donde $\alpha$ es alrededor de $0.2-0.25$ . El límite inferior de la entropía $\lceil{\log((N-1)!)/\log(M!)}\rceil$ con los mismos parámetros es $0,1,3,5,7,10,13,16,19.$
