Consideremos el algoritmo obvio para comprobar si una lista de enteros está ordenada: se empieza por el principio de la lista y se recorre hasta hasta que encontremos un par de elementos sucesivos que estén desordenados. En ese caso, devuelve false. Si no se encuentra ninguna pareja de este tipo al llegar al final de la lista, devolvemos true. Supongamos que la lista de entrada es una permutación aleatoria de $1, 2, \ldots, N$ y todas esas permutaciones son igualmente probables. Deducir el caso medio tiempo de ejecución esperado. Dé una respuesta exacta y asintótica.
La complejidad de una lista determinada depende del momento en que se encuentre el primer par de elementos fuera de orden. Sea $c_N\left(n\right)=n$ sea la complejidad de una lista en la que el $n$ es el primero que está fuera de orden.
Dejemos que $p_N\left(n\right)$ sea la probabilidad de que el $n$ La segunda pareja de la lista es la primera que está fuera de orden.
Entonces entiendo que la complejidad media del caso viene dada por $\sum_{n=1}^{N-1} p_N\left(n\right)c_N\left(n\right) + \left(1 - \sum_{n=1}^{N-1} p_N\left(n\right)\right) \left(N-1\right)$ .
Sin embargo, he estado luchando para derivar $p_N\left(n\right)$ . Trabajando a mano una serie de ejemplos, he identificado que $p_N\left(n\right) = \frac{1}{a\left(n\right)}$ , donde $a\left(n\right) = n! + \left(n-1\right)!$ es la secuencia A001048 .
He intentado hacer ingeniería inversa de una derivación reconociendo que $p_N\left(n\right) = \frac{f_N\left(n\right)}{N!}$ , donde $f_N\left(n\right)$ es el número de listas cuyo $n$ es el primero que está fuera de orden. El álgebra muestra que $f_N\left(n\right) = n \frac{N!}{\left(n+1\right)!}$ pero lamentablemente no puedo ver cómo se derivaría este término.
Agradecería cualquier pista. ¡Gracias de antemano por su ayuda!
P.D. También he descubierto a través de WolframAlpha la interesante propiedad que $\sum_{n=1}^\infty p_N\left(n\right)c_N\left(n\right) = e - 1$ .
