c++ - La complejidad amortizada de std:: next_permutation?
algorithm stl (3)
Acabo de leer esta otra pregunta sobre la complejidad de next_permutation y aunque estoy satisfecho con la respuesta (O (n)), parece que el algoritmo puede tener un buen análisis amortizado que muestra una menor complejidad. ¿Alguien sabe de tal análisis?
Aquí n representa el recuento de elementos en el contenedor, no el recuento total de posibles permutaciones. El algoritmo debe recorrer un orden de todos los elementos en cada llamada; toma un par de iteradores bidireccionales, lo que implica que para llegar a un elemento, el algoritmo debe visitar primero el anterior (a menos que sea el primero o el último elemento). Un iterador bidireccional permite la iteración hacia atrás, por lo que el algoritmo puede (de hecho, debe) realizar la mitad de swaps que elementos. Creo que la norma podría ofrecer una sobrecarga para un iterador hacia adelante, que admitiría iteradores más tontos a costa de n swaps en lugar de media n swaps. Pero, por desgracia, no fue así.
Por supuesto, para n posibles permutaciones, el algoritmo opera en O (1).
No estoy realmente seguro de la implementación exacta de std :: next_permutation, pero si es el mismo que el algoritmo de Narayana Pandita que se describe en el wiki aquí: http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations ,
asumiendo que los elementos son distintos, ¡parece que está O (1) amortizado! (Por supuesto, puede haber errores en el siguiente)
Contemos el número total de swaps realizados.
Obtenemos la relación de recurrencia.
T (n + 1) = (n + 1) T (n) + Θ (n 2 )
(n + 1) T (n) viene de arreglar el primer elemento y hacer los swaps para la n restante.
Θ (n 2 ) viene de cambiar el primer elemento. En el momento en que cambiamos el primer elemento, hacemos sw (n) swaps. Hacer eso n veces, obtienes Θ (n 2 ).
Ahora vamos a X(n) = T(n)/n!
Entonces conseguimos
X (n + 1) = X (n) + Θ (n 2 ) / (n + 1)!
es decir, hay una constante C tal que
X (n + 1) <= X (n) + Cn 2 / (n + 1)!
Escribir n tales desigualdades nos da
X (n + 1) - X (n) <= Cn 2 / (n + 1)!
X (n) - X (n-1) <= C (n-1) 2 / (n)!
X (n-1) - X (n-2) <= C (n-2) 2 / (n-1)!
...
X (2) - X (1) <= C1 2 / (1 + 1)!
Sumar estos valores nos da X(n+1) - X(1) <= C(/sum j = 1 to n (j^2)/(j+1)!) .
Desde la serie infinita /sum j = 1 to infinity j^2/(j+1)! converge a C '', digamos, obtenemos X(n+1) - X(1) <= CC''
Recuerde que X (n) cuenta el número promedio de swaps necesarios (T (n) / n!)
Así, el número promedio de swaps es O (1).
Dado que la búsqueda de los elementos a intercambiar es lineal con el número de swaps, se amortiza O (1) incluso si se tienen en cuenta otras operaciones.
Así que parece que voy a responder mi propia pregunta de forma afirmativa: sí , next_permutation ejecuta en O (1) tiempo amortizado.
Antes de entrar en una prueba formal de esto, aquí hay un rápido repaso de cómo funciona el algoritmo. Primero, escanea hacia atrás desde el final del rango hacia el principio, identificando la subsecuencia decreciente contigua más larga en el rango que termina en el último elemento. Por ejemplo, en 0 3 4 2 1 , el algoritmo identificaría 4 2 1 como esta subsecuencia. A continuación, observa el elemento justo antes de esta subsecuencia (en el ejemplo anterior, 3), luego encuentra el elemento más pequeño en la subsecuencia más grande que él (en el ejemplo anterior, 4). Luego intercambia las posiciones de esos dos elementos y luego invierte la secuencia identificada. Entonces, si empezáramos con 0 3 4 2 1 , intercambiaríamos el 3 y el 4 para obtener 0 4 3 2 1 , y luego revertiríamos los últimos tres elementos para producir 0 4 1 2 3 .
Para mostrar que este algoritmo se ejecuta en O (1) amortizado, utilizaremos el método potencial. Defina Φ para que sea tres veces la longitud de la subsecuencia decreciente contigua más larga al final de la secuencia. En este análisis, asumiremos que todos los elementos son distintos. Dado esto, pensemos en el tiempo de ejecución de este algoritmo. Supongamos que exploramos hacia atrás desde el final de la secuencia y encontramos que los últimos m elementos son parte de la secuencia decreciente. Esto requiere m + 1 comparaciones. A continuación, encontramos, de los elementos de esa secuencia, cuál es el más pequeño más grande que el elemento que precede a esta secuencia. Esto toma, en el peor de los casos, un tiempo proporcional a la longitud de la secuencia decreciente utilizando un escaneo lineal para otras comparaciones de m. Intercambiar los elementos toma, digamos, la cantidad de tiempo de 1 crédito, y revertir la secuencia requiere, a lo sumo, más operaciones. Por lo tanto, el tiempo de ejecución real de este paso es aproximadamente 3m + 1. Sin embargo, tenemos que tener en cuenta el cambio en el potencial. Después de revertir esta secuencia de longitud m, terminamos reduciendo la longitud de la secuencia decreciente más larga al final del rango para que sea la longitud 1, porque al invertir la secuencia decreciente al final, los últimos elementos del rango se clasifican en orden ascendente . Esto significa que nuestro potencial cambió de Φ = 3m a Φ ''= 3 * 1 = 3. En consecuencia, la caída neta en el potencial es de 3 - 3m, por lo que nuestro tiempo amortizado neto es de 3m + 1 + (3 - 3m) = 4 = O (1).
En el análisis anterior hice el supuesto simplificador de que todos los valores son únicos. Que yo sepa, esta suposición es necesaria para que esta prueba funcione. Voy a pensar en esto y ver si se puede modificar la prueba para que funcione en el caso en que los elementos puedan contener duplicados, y publicaré una edición en esta respuesta una vez que haya revisado los detalles.