algorithm - ordenada - listas enlazadas java
¿Por qué aumentar el puntero por dos mientras busca el bucle en la lista vinculada, por qué no el 3,4,5? (6)
Ya eché un vistazo a la question que habla de algoritmo para encontrar el bucle en una lista vinculada. He leído la solución de algoritmo de búsqueda de ciclos de Floyd , mencionada en muchos lugares donde tenemos que tomar dos punteros. Un puntero (más lento / tortuga) se incrementa en uno y el otro puntero (más rápido / liebre) se aumenta en 2. Cuando son iguales, encontramos el ciclo y si el puntero más rápido llega a cero, no hay ningún ciclo en la lista enlazada.
Ahora mi pregunta es por qué aumentamos el puntero más rápido por 2. ¿Por qué no otra cosa? Es necesario aumentar en 2 o podemos aumentarlo en X para obtener el resultado. ¿Es necesario que encontremos un bucle si incrementamos el puntero más rápido en 2 o puede haber el caso en el que necesitamos incrementar en 3 o 5 o x?
Considere un ciclo de tamaño L, lo que significa que en el elemento k es donde está el lazo: x k -> x k + 1 -> ... -> x k + L-1 -> x k . Supongamos que un puntero se ejecuta a la velocidad r 1 = 1 y el otro en r 2 . Cuando el primer puntero alcanza x k, el segundo puntero ya estará en el bucle en algún elemento x k + s, donde 0 <= s <L. Después de m el siguiente puntero se incrementa, el primer puntero está en x k + (m mod L) y el el segundo puntero está en x k + ((m * r 2 + s) mod L) . Por lo tanto, la condición de que los dos indicadores colisionen se puede expresar como la existencia de un m que satisfaga la congruencia
m = m * r 2 + s (mod L)
Esto se puede simplificar con los siguientes pasos
m (1-r 2 ) = s (mod L)
m (L + 1-r 2 ) = s (mod L)
Esto tiene la forma de una congruencia lineal. Tiene una solución m si s es divisible por gcd (L + 1-r 2 , L). Este será sin duda el caso si gcd (L + 1-r 2 , L) = 1. Si r 2 = 2, entonces gcd (L + 1-r 2 , L) = gcd (L-1, L) = 1 y siempre existe una solución m.
Así, r 2 = 2 tiene la buena propiedad de que para cualquier tamaño de ciclo L satisface gcd (L + 1-r 2 , L) = 1 y garantiza que los punteros eventualmente colisionarán incluso si los dos punteros comienzan en diferentes ubicaciones. Otros valores de r 2 no tienen esta propiedad.
No hay ninguna razón por la que necesite usar el número dos. Cualquier elección de tamaño de paso funcionará (excepto uno, por supuesto).
Para ver por qué funciona esto, echemos un vistazo a por qué funciona el algoritmo de Floyd en primer lugar. La idea es pensar en la secuencia x 0 , x 1 , x 2 , ..., x n , ... de los elementos de la lista vinculada que visitarás si comienzas desde el principio de la lista y luego sigue caminando hasta que llegues al final. Si la lista no contiene un ciclo, todos estos valores son distintos. Si contiene un ciclo, entonces, esta secuencia se repetirá sin fin.
Aquí está el teorema que hace que el algoritmo de Floyd funcione:
La lista enlazada contiene un ciclo si y solo si hay un entero positivo j tal que para cualquier entero positivo k, x j = x jk .
Vamos a probar esto; no es tan dificil. Para el caso "si", si tal aj existe, elija k = 2. Entonces tenemos eso para algunos positivos j, x j = x 2j y j ≠ 2j, y entonces la lista contiene un ciclo.
En la otra dirección, suponga que la lista contiene un ciclo de longitud l que comienza en la posición s. Deje j ser el múltiplo más pequeño de l mayor que s. Entonces para cualquier k, si consideramos x j y x jk , ya que j es un múltiplo de la longitud del bucle, podemos pensar en x jk como el elemento formado comenzando en la posición j en la lista, luego tomando j pasos k-1 veces. Pero cada una de estas veces que realiza j pasos, termina justo donde comenzó en la lista porque j es un múltiplo de la longitud del bucle. En consecuencia, x j = x jk .
Esta prueba le garantiza que si toma un número constante de pasos en cada iteración, de hecho golpeará el puntero lento. Más precisamente, si está tomando k pasos en cada iteración, eventualmente encontrará los puntos x j y x kj y detectará el ciclo. Intuitivamente, las personas tienden a elegir k = 2 para minimizar el tiempo de ejecución, ya que se toma el menor número de pasos en cada iteración.
Podemos analizar el tiempo de ejecución más formalmente de la siguiente manera. Si la lista no contiene un ciclo, el puntero rápido tocará el final de la lista después de n pasos para O (n) tiempo, donde n es el número de elementos en la lista. De lo contrario, los dos punteros se encontrarán después de que el puntero lento haya tomado j pasos. Recuerde que j es el múltiplo más pequeño de l mayor que s. Si s ≤ l, entonces j = l; de lo contrario, si s> l, entonces j será como máximo 2s, y entonces el valor de j es O (s + l). Como l y s no pueden ser mayores que la cantidad de elementos en la lista, esto significa que j = O (n). Sin embargo, después de que el puntero lento haya tomado j pasos, el puntero rápido habrá tomado k pasos para cada uno de los j pasos realizados por el puntero más lento, por lo que habrá tomado O (kj) pasos. Como j = O (n), el tiempo de ejecución neto es como máximo O (nk). Tenga en cuenta que esto indica que cuantos más pasos realicemos con el puntero rápido, más tardará el algoritmo en finalizar (aunque solo de forma proporcional). Escoger k = 2 minimiza así el tiempo de ejecución general del algoritmo.
¡Espero que esto ayude!
Si el puntero rápido se mueve 3 pasos y el puntero lento en 1 paso, no se garantiza que ambos punteros se encuentren en ciclos que contienen un número par de nodos. Sin embargo, si el puntero lento se moviera en 2 pasos, la reunión estaría garantizada.
En general, si la liebre se mueve en H pasos, y la tortuga se mueve en T pasos, se garantiza que se encontrarán en un ciclo si f H = T + 1 .
Considere la liebre en movimiento en relación con la tortuga.
- La velocidad de Hare con respecto a la tortuga es
H - Tnodos por iteración. Dado un ciclo de longitud
N =(H - T) * k, dondekes cualquier entero positivo, la liebre omitirá todos los nodosH - T - 1(nuevamente, en relación con la tortuga), y sería imposible para ellos para cumplir si la tortuga estaba en alguno de esos nodos.La única posibilidad donde se garantiza una reunión es cuando
H - T - 1 = 0.
Por lo tanto, se permite aumentar el puntero rápido en x , siempre que el puntero lento aumente en x - 1 .
Si hay un bucle (de n nodos), una vez que un puntero ha ingresado al bucle, permanecerá allí para siempre; para que podamos avanzar en el tiempo hasta que ambos punteros estén en el bucle. A partir de aquí, los punteros se pueden representar mediante enteros módulo n con los valores iniciales a y b. La condición para que se reúnan después de t pasos es entonces
a + t≡b + 2t mod n que tiene solución t = a-b mod n.
Esto funcionará siempre que la diferencia entre las velocidades no comparta factores primos con n.
La única restricción en las velocidades es que su diferencia debe ser coprima con la longitud del bucle.
Si la lista enlazada tiene un bucle, un puntero rápido con un incremento de 2 funcionará mejor que un incremento de 3 o 4 o más porque asegura que una vez que estemos dentro del bucle, los punteros seguramente colisionarán y no habrá adelantamiento.
Por ejemplo, si tomamos el incremento de 3 y dentro del bucle asumiremos
fast pointer --> i
slow --> i+1
the next iteration
fast pointer --> i+3
slow --> i+2
mientras que tal caso nunca ocurrirá con un incremento de 2.
Además, si tiene mucha mala suerte, puede terminar en una situación en la que la longitud del bucle sea L y aumente el puntero rápido en L+1 . Entonces estarás trabado infinitamente ya que la diferencia del movimiento rápido y el puntero lento siempre serán L
Espero haber sido claro.
Supongamos que la longitud de la lista que no contiene el bucle sea s , la longitud del bucle be t y la relación de fast_pointer_speed a slow_pointer_speed be k .
Deje que los dos punteros se encuentren a una distancia j desde el inicio del ciclo.
Entonces, la distancia que recorre el puntero lento = s + j . Distancia que recorre el puntero rápido = s + j + m * t (donde m es el número de veces que el puntero rápido ha completado el ciclo). Pero, el puntero rápido también habría recorrido una distancia k * (s + j) ( k la distancia del puntero lento).
Por lo tanto, obtenemos k * (s + j) = s + j + m * t .
s + j = (m / k-1)t .
Por lo tanto, a partir de la ecuación anterior, la longitud que recorre el puntero lento es un múltiplo entero de la longitud del bucle.
Para una mayor eficiencia, (m / k-1) = 1 (el puntero lento no debería haber recorrido el circuito más de una vez).
por lo tanto, m = k - 1 => k = m + 1
Como m es el número de veces que el puntero rápido ha completado el ciclo, m >= 1 . Para una mayor eficiencia, m = 1 .
por lo tanto, k = 2 .
si tomamos un valor de k > 2 , más la distancia que tendrían que recorrer los dos punteros.
Espero que la explicación anterior ayude.