Subsecuencia creciente más larga

En informática , el problema de la subsecuencia creciente más larga tiene como objetivo encontrar una subsecuencia de una secuencia dada en la que los elementos de la subsecuencia estén ordenados en orden ascendente y en la que la subsecuencia sea lo más larga posible. Esta subsecuencia no tiene por qué ser contigua ni única. Las subsecuencias crecientes más largas se estudian en el contexto de diversas disciplinas relacionadas con las matemáticas , incluyendo la algoritmia , la teoría de matrices aleatorias , la teoría de la representación y la física . ^{[ 1 ] [ 2 ]} El problema de la subsecuencia creciente más larga es resoluble en tiempo${\displaystyle O(n\log n),}$dónde${\displaystyle n}$denota la longitud de la secuencia de entrada. ^{[ 3 ]}

En los primeros 16 términos de la secuencia binaria de Van der Corput

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

una de las subsecuencias crecientes más largas es

0, 2, 6, 9, 11, 15.

Esta subsecuencia tiene una longitud de seis; la secuencia de entrada no tiene subsecuencias crecientes de siete miembros. La subsecuencia creciente más larga en este ejemplo no es la única solución: por ejemplo,

0, 4, 6, 9, 11, 15

0, 2, 6, 9, 13, 15

0, 4, 6, 9, 13, 15

son otras subsecuencias crecientes de igual longitud en la misma secuencia de entrada.

El problema de la subsecuencia creciente más larga está estrechamente relacionado con el problema de la subsecuencia común más larga , que tiene una solución de programación dinámica de tiempo cuadrático : la subsecuencia creciente más larga de una secuencia.${\displaystyle S}$es la subsecuencia común más larga de${\displaystyle S}$y${\displaystyle T,}$dónde${\displaystyle T}$es el resultado de la clasificación${\displaystyle S.}$Sin embargo, para el caso especial en el que la entrada es una permutación de los enteros${\displaystyle 1,2,\ldots ,n,}$Este enfoque puede hacerse mucho más eficiente, lo que lleva a límites de tiempo de la forma${\displaystyle O(n\log \log n).}$^{[ 4 ]}

La camarilla más grande en un grafo de permutación corresponde a la subsecuencia decreciente más larga de la permutación que define el grafo (suponiendo que la secuencia original no permutada está ordenada de menor a mayor valor). De manera similar, el conjunto independiente máximo en un grafo de permutación corresponde a la subsecuencia no decreciente más larga. Por lo tanto, los algoritmos de subsecuencia creciente más larga pueden utilizarse para resolver el problema de la camarilla de manera eficiente en grafos de permutación. ^{[ 5 ]}

En la correspondencia de Robinson-Schensted entre permutaciones y tablas de Young , la longitud de la primera fila de la tabla correspondiente a una permutación es igual a la longitud de la subsecuencia creciente más larga de la permutación, y la longitud de la primera columna es igual a la longitud de la subsecuencia decreciente más larga. ^{[ 3 ]}

El algoritmo que se describe a continuación resuelve eficientemente el problema de la subsecuencia creciente más larga con arreglos y búsqueda binaria . Procesa los elementos de la secuencia en orden, manteniendo la subsecuencia creciente más larga encontrada hasta el momento. Denotemos los valores de la secuencia como${\displaystyle X[0],X[1],\ldots ,}$etc. Luego, después del procesamiento${\displaystyle X[i],}$El algoritmo habrá almacenado un número entero.${\displaystyle L}$y valores en dos matrices:

• ${\displaystyle L}$— almacena la longitud de la subsecuencia creciente más larga encontrada hasta el momento.
• ${\displaystyle M[l]}$— almacena el índice${\displaystyle k}$del valor más pequeño${\displaystyle X[k]}$de tal manera que exista una subsecuencia creciente de longitud${\displaystyle l}$terminando en${\displaystyle X[k]}$en el rango${\displaystyle k\leq i.}$Explícitamente, supongamos que${\displaystyle K_{i,l}}$denota el conjunto de todos los índices${\displaystyle j}$de tal manera que${\displaystyle j\leq i}$y existe una subsecuencia creciente de longitud${\displaystyle l}$terminando en${\displaystyle X[j].}$Entonces${\displaystyle k=M[l]}$es el índice en${\displaystyle K_{i,l}}$para qué${\displaystyle X[M[l]]}$se minimiza; lo que significa que${\displaystyle M[l]\in K_{i,l}}$y${\displaystyle X[M[l]]=\min _{j\in K_{i,l}}X[j]}$(o equivalentemente,${\displaystyle M[l]\in K_{i,l}}$y por cada${\displaystyle j\in K_{i,l},}$${\displaystyle X[M[l]]\leq X[j]}$); si varios índices satisfacen esta condición entonces${\displaystyle M[l]}$es el más grande.
  • Para aclarar, "existe una subsecuencia creciente de longitud${\displaystyle l}$terminando en${\displaystyle X[k]}$" significa que existen${\displaystyle l}$índices${\displaystyle i_{1}<i_{2}<\cdots <i_{l}=k}$terminando en${\displaystyle k}$de tal manera que${\displaystyle X\left[i_{1}\right]<X\left[i_{2}\right]<\cdots <X[k].}$
  • Tenga en cuenta que${\displaystyle 1\leq l\leq i+1,}$porque${\displaystyle l\geq 1}$representa la longitud de la subsecuencia creciente, y${\displaystyle k\geq 0}$representa el índice de su terminación.
  • La longitud de${\displaystyle M}$es${\displaystyle 1}$más que la longitud de${\displaystyle X}$pero es posible que no todos los elementos de este array sean utilizados por el algoritmo (de hecho, si la secuencia creciente más larga tiene longitud${\displaystyle L}$entonces solo${\displaystyle M[1],\ldots ,M[L]}$son utilizados por el algoritmo). Sin embargo, si${\displaystyle M[l]}$entonces se utiliza/define${\displaystyle l-1\leq M[l]}$(y además, en cada iteración)${\displaystyle i,}$${\displaystyle M[l]\leq i}$también se mantendrá).${\displaystyle M[0]}$no está definido ya que las secuencias de longitud${\displaystyle 0}$no tienen índice final (${\displaystyle M[0]}$puede ser cualquier valor).
• ${\displaystyle P[k]}$— almacena el índice del predecesor de${\displaystyle X[k]}$en la subsecuencia creciente más larga que termina en${\displaystyle X[k].}$
  • La longitud de${\displaystyle P}$es igual a la de${\displaystyle X,}$
  • Si${\displaystyle k>0}$entonces${\displaystyle P[k]<k}$mientras${\displaystyle P[0]}$no está definido desde${\displaystyle X[0]}$no tiene predecesor (${\displaystyle P[0]}$puede ser cualquier valor).

Dado que el algoritmo que se muestra a continuación utiliza numeración basada en cero , para mayor claridad${\displaystyle M}$está acolchado con${\displaystyle M[0],}$que queda sin usar para que${\displaystyle M[l]}$corresponde a una subsecuencia de longitud${\displaystyle l.}$Una implementación real puede omitir${\displaystyle M[0]}$y ajustar los índices en consecuencia.

Tenga en cuenta que, en cualquier punto del algoritmo, la secuencia $${\displaystyle X[M[1]],X[M[2]],\ldots ,X[M[L]]}$$ es creciente. Porque, si hay una subsecuencia creciente de longitud${\displaystyle l\geq 2}$terminando en${\displaystyle X[M[l]],}$entonces también hay una subsecuencia de longitud${\displaystyle l-1}$terminando en un valor menor: es decir, el que termina en${\displaystyle X[P[M[l]]].}$Por lo tanto, podemos realizar búsquedas binarias en esta secuencia en tiempo logarítmico.

El algoritmo procede entonces de la siguiente manera:

P = matriz de longitud N M = matriz de longitud N + 1 M[0] = -1 // indefinido, por lo que se puede establecer en cualquier valor. L = 0 para i en el rango de 0 a N-1: //N-1 incluido // Búsqueda binaria del l ≤ L positivo más pequeño // tal que X[M[l]] >= X[i] lo = 1 hi = L + 1 mientras lo < hi: medio = lo + piso((hi-lo)/2) // lo <= medio < hi si X[M[mid]] >= X[i] alto = medio else : // si X[M[mid]] < X[i] lo = medio + 1 // Después de buscar, lo == hi es 1 mayor que el // longitud del prefijo más largo de X[i] nuevoL = lo // El predecesor de X[i] es el último índice de // la subsecuencia de longitud newL-1 P[i] = M[newL-1] M[newL] = i Si newL > L: // Si encontramos una subsecuencia más larga que cualquiera que hayamos encontrado // encontrado todavía, actualizar L L = nuevoL // Reconstruir la subsecuencia creciente más larga // Consiste en los valores de X en los índices L: // ..., P[P[M[L]]], P[M[L]], M[L] S = matriz de longitud L k = M[L] para j en el rango L-1 a 0: //0 incluido S[j] = X[k] k = P[k] devolver S

Debido a que el algoritmo realiza una única búsqueda binaria por elemento de la secuencia, su tiempo total se puede expresar utilizando la notación Big O como${\displaystyle O(n\log n).}$Fredman (1975) analiza una variante de este algoritmo, que atribuye a Donald Knuth ; en la variante que estudia, el algoritmo comprueba si cada valor${\displaystyle X[i]}$puede utilizarse para extender la secuencia creciente más larga actual, en tiempo constante, antes de realizar la búsqueda binaria. Con esta modificación, el algoritmo utiliza como máximo${\displaystyle n\log _{2}n-n\log _{2}\log _{2}n+O(n)}$comparaciones en el peor de los casos, que es óptimo para un algoritmo basado en comparaciones hasta el factor constante en el${\displaystyle O(n)}$término. ^{[ 6 ]}

Ejemplo de ejecución

Según el teorema de Erdős-Szekeres , cualquier secuencia de${\displaystyle n^{2}+1}$distintos enteros tienen una subsecuencia creciente o decreciente de longitud${\displaystyle n+1.}$^{[ 7 ] [ 8 ]} Para entradas en las que cada permutación de la entrada es igualmente probable, la longitud esperada de la subsecuencia creciente más larga es aproximadamente${\displaystyle 2{\sqrt {n}}.}$^{[ 9 ] [ 2 ]}

En el límite como${\displaystyle n}$El teorema de Baik-Deift-Johansson dice que la longitud de la subsecuencia creciente más larga de una secuencia aleatoriamente permutada de${\displaystyle n}$Los elementos tienen una distribución que se aproxima a la distribución de Tracy-Widom , la distribución del mayor valor propio de una matriz aleatoria en el conjunto unitario gaussiano . ^{[ 10 ]}

La subsecuencia creciente más larga también se ha estudiado en el contexto de algoritmos en línea , en los que los elementos de una secuencia de variables aleatorias independientes con distribución continua${\displaystyle F}$– o alternativamente los elementos de una permutación aleatoria – se presentan uno a la vez a un algoritmo que debe decidir si incluir o excluir cada elemento, sin conocimiento de los elementos posteriores. En esta variante del problema, que permite aplicaciones interesantes en varios contextos, es posible diseñar un procedimiento de selección óptimo que, dada una muestra aleatoria de tamaño${\displaystyle n}$como entrada, generará una secuencia creciente con una longitud máxima esperada de tamaño aproximado${\displaystyle {\sqrt {2n}}.}$^{[ 11 ]} La longitud de la subsecuencia creciente seleccionada por este procedimiento óptimo tiene una varianza aproximadamente igual a${\displaystyle {\sqrt {2n}}/3,}$y su distribución límite es asintóticamente normal después del centrado y escalado habituales. ^{[ 12 ]} Los mismos resultados asintóticos se mantienen con límites más precisos para el problema correspondiente en el contexto de un proceso de llegada de Poisson . ^{[ 13 ]} Un refinamiento adicional en el contexto del proceso de Poisson se da a través de la demostración de un teorema del límite central para el proceso de selección óptimo que se cumple, con una normalización adecuada, en un sentido más completo de lo que cabría esperar. La demostración produce no solo el teorema del límite funcional "correcto", sino también la matriz de covarianza (singular) del proceso tridimensional que resume todos los procesos interactuantes. ^{[ 14 ]}

• Anatoly Vershik, quien estudió aplicaciones de la teoría de grupos a las subsecuencias crecientes más largas en permutaciones aleatorias. ^{[ 15 ]}
• Subsecuencia alternante más larga
• Subsecuencia común más larga
• Clasificación por paciencia : una técnica eficiente para encontrar la longitud de la subsecuencia creciente más larga.
• Monoide plástico : un sistema algebraico definido por transformaciones que preservan la longitud de la subsecuencia creciente más larga.

• Subsecuencia creciente más larga del algoritmo
• Subsecuencia creciente más larga simplificada
• Encontrar el número de subsecuencias incrementadas más largas