Para responder a la pregunta real, la longitud esperada de la subsecuencia creciente más larga en una permutación aleatoria de elementos [math] n [/ math] es asintóticamente igual a [math] 2 \ sqrt {n} [/ math]. (Consulte, por ejemplo, http://www.dtc.umn.edu/~odlyzko/… para obtener una descripción general de algunos resultados relacionados).
Si genera [math] n [/ math] números aleatorios independientes de U (0,1), obtendrá cada permutación con probabilidad [math] 1 / n! [/ Math] y cada no permutación con probabilidad 0, entonces ese es esencialmente el mismo caso.
Ahora déjame abordar la pregunta que mencionaste en los detalles de la pregunta.
- ¿Qué significa que un problema en informática sea NP completo?
- ¿Cuánta programación necesito saber si quería ingresar a la criptografía?
- ¿En qué se diferencia la informática de las matemáticas para resolver un problema?
- ¿Es la 'prueba' del teorema de Demorgan dada en los libros de texto una 'prueba' o una 'verificación'?
- ¿Qué es la función mágica en MATLAB?
Tenga en cuenta que, por lo general, es una buena idea hacer la pregunta que desea hacer, en este caso sería “¿Cómo puedo verificar mi implementación de un algoritmo de subsecuencia cada vez mayor?” Si otra persona tiene la misma pregunta, ahora tendrá más dificultades para encontrar esta respuesta. (Con suerte, mencionar la pregunta podría ayudar 😉)
Dicho esto, aquí hay algunas sugerencias.
Su forma de prueba parece insuficiente. En primer lugar, nunca se prueba la corrección. Debes hacer eso. Está descartando la fuerza bruta, pero en realidad es una forma sensata: como su algoritmo probablemente no tiene un caso especial para las entradas pequeñas (y ninguno de los algoritmos LIS que he visto lo hace), si su implementación resulta ser incorrecta en general , es casi seguro que también está mal para entradas pequeñas. Y es perfectamente factible generar entradas aleatorias de longitud, digamos 15, resolver cada una de ellas utilizando la fuerza bruta (verifique cada una de las subsecuencias 2 ^ 15) y utilizando su algoritmo, y compare los resultados.
Además, cuando digo “entradas aleatorias”, no me refiero a su tipo de entradas aleatorias. Probablemente se esté perdiendo por completo lo más importante para probar: si su algoritmo se comporta correctamente si hay múltiples elementos con el mismo valor en la entrada. Las pruebas en secuencias de enteros aleatorios pequeños son mucho mejores.
Solo después de tales pruebas de corrección debe probar en entradas grandes (tanto aleatorias como no aleatorias) la eficiencia. (La prueba solo en entradas aleatorias es, una vez más, insuficiente: hay muchos algoritmos que son eficientes en la expectativa en las entradas aleatorias, pero tienen una complejidad estrictamente peor en el peor de los casos).
Finalmente, el teorema de Erdős-Szekeres debería darle una forma estrictamente mejor de hacer una prueba “estadística”: dada una secuencia, use su algoritmo dos veces para calcular su LIS y LDS (que es LIS si niega todos los valores), y verifique si producto de su longitud es lo suficientemente grande.
