Зачем увеличивать указатель на два при поиске цикла в связанном списке, а не 3,4,5?

Question

Я уже рассмотрел вопрос , в котором рассказывается об алгоритме поиска цикла в связанном списке. Я прочитал алгоритм поиска цикла Флойда , упомянутое во многих местах, где нам нужно взять два указателя. Один указатель (медленнее / черепаха) увеличивается на один, а другой указатель (быстрее / заяц) увеличивается на 2. Когда они равны, мы находим цикл, и если более быстрый указатель достигает нуля, в связанном списке петли нет.

Теперь мой вопрос: почему мы увеличиваем более быстрый указатель на 2. Почему не что-то еще? Увеличение на 2 необходимо, или мы можем увеличить его на X, чтобы получить результат. Нужно ли искать цикл, если мы увеличиваем более быстрый указатель на 2, или может быть случай, когда нам нужно увеличить на 3, 5 или x.

Answer 1

Нет причин, по которым вам нужно использовать номер два. Подойдет любой размер шага (конечно, кроме одного).

Чтобы увидеть, почему это работает, давайте посмотрим, почему алгоритм Флойда работает в первую очередь. Идея состоит в том, чтобы подумать о последовательности x ₀ , x ₁ , x ₂ , ..., x _n , .. из элементов связанного списка, который вы посетите, если начнете с начала списка, а затем продолжите идти по нему, пока не дойдете до конца. Если список не содержит цикл, то все эти значения различны. Если же он содержит цикл, то эта последовательность будет повторяться бесконечно.

Вот теорема, которая заставляет алгоритм Флойда работать:

Связанный список содержит цикл тогда и только тогда, когда существует положительное целое число j, такое что для любого положительного целого числа k, x _j = x _jk .

Давай докажем это; это не так сложно. Для случая «если», если такой j существует, выберите k = 2. Тогда мы получим это для некоторых положительных j, x _j = x _2j и j & ne; 2j, и поэтому список содержит цикл.

Для другого направления предположим, что список содержит цикл длиной l, начинающийся с позиции s. Пусть j будет наименьшим кратным l больше s. Тогда для любого k, если мы рассмотрим x _j и x _jk , так как j кратно длине цикла, мы можем думать о x _jk как Элемент формируется, начиная с позиции j в списке, затем делая j шагов k-1 раз. Но каждый раз, когда вы делаете j шагов, вы в конечном итоге возвращаетесь к тому, с чего начинали в списке, потому что j кратно длине цикла. Следовательно, x _j = x _jk .

Это доказательство гарантирует вам, что если вы выполните какое-либо постоянное число шагов на каждой итерации, вы действительно нажмете на медленный указатель. Точнее, если вы делаете k шагов на каждой итерации, то в конечном итоге вы найдете точки x _j и x _kj и обнаружите цикл. Интуитивно понятно, что люди, как правило, выбирают k = 2, чтобы минимизировать время выполнения, поскольку на каждой итерации вы выполняете наименьшее количество шагов.

Мы можем проанализировать время выполнения более формально следующим образом. Если список не содержит цикла, быстрый указатель достигнет конца списка после n шагов в течение O (n) времени, где n - количество элементов в списке. В противном случае два указателя встретятся после того, как медленный указатель предпримет j шагов. Помните, что j является наименьшим кратным l больше s. Если s & le; l, тогда j = l; в противном случае, если s> l, то j будет не более 2 с, и поэтому значение j равно O (s + l). Поскольку l и s не могут превышать количество элементов в списке, это означает, что j = O (n). Однако после того, как медленный указатель сделал j шагов, быстрый указатель сделает k шагов для каждого из j шагов медленного указателя, поэтому он предпримет O (kj) шагов. Поскольку j = O (n), чистая среда выполнения не более O (nk). Обратите внимание, что это говорит о том, что чем больше шагов мы сделаем с помощью быстрого указателя, тем дольше алгоритм завершает работу (хотя и пропорционально). Выбор k = 2, таким образом, минимизирует общее время выполнения алгоритма.

Надеюсь, это поможет!

Answer 2

Предположим, что длина списка, не содержащего цикл, равна s, длина цикла равна t, а отношение fast_pointer_speed к slow_pointer_speed равно k.

Пусть два указателя встречаются на расстоянии j от начала цикла.

Итак, медленный указатель расстояния перемещается = s + j.Расстояние, на которое перемещается быстрый указатель = s + j + m * t (где m - количество раз, которое быстрый указатель завершил цикл).Но быстрый указатель также прошел бы расстояние k * (s + j) (k, умноженное на расстояние медленного указателя).

Следовательно, мы получаем k * (s + j) = s + j + m * t.

s + j = (m / k-1)t.

Следовательно, из приведенного выше уравнения длина, на которую перемещается медленный указатель, является целым кратным длины цикла.

Для наибольшей эффективности (m / k-1) = 1 (медленный указатель не должен был перемещатьсяцикл более одного раза.)

поэтому m = k - 1 => k = m + 1

Поскольку m - это число раз, которое быстрый указатель завершил цикл, m >= 1.Для максимальной эффективности m = 1.

, следовательно, k = 2.

, если мы примем значение k > 2, больше расстояние, которое должны пройти два указателя.

Надеюсь, приведенное выше объяснение поможет.

Answer 3

Рассмотрим цикл размера L, означающий, что в элементе k находится цикл: x _k -> x _{k + 1} -> ... -> x _{k + L-1} -> x _k . Предположим, что один указатель работает со скоростью r ₁ = 1, а другой - со скоростью r ₂ . Когда первый указатель достигает x _k , второй указатель уже будет в цикле в некотором элементе x _{k + s} , где 0 <= s <L. После m дальнейший указатель увеличивает первый указатель находится в x <sub>k + (m mod L) , а второй указатель в x _{k + ((m * r 2 + s) mod L)} . Поэтому условие, что два указателя сталкиваются, можно сформулировать как существование m, удовлетворяющего конгруэнтности

m = m * r ₂ + s (мод L)

Это можно упростить с помощью следующих шагов

м (1-р ₂ ) = с (мод L)

м (L + 1-r ₂ ) = s (мод L)

Это имеет форму линейного сравнения. Он имеет решение m, если s делится на gcd (L + 1-r ₂ , L). Это, безусловно, будет иметь место, если gcd (L + 1-r ₂ , L) = 1. Если r ₂ = 2, то gcd (L + 1-r ₂ , L) = gcd (L-1, L) = 1 и решение m всегда существует.

Таким образом, r ₂ = 2 обладает хорошим свойством, что для любого размера цикла L он удовлетворяет gcd (L + 1-r ₂ , L) = 1 и, таким образом, гарантирует, что указатели со временем столкнутся, даже если два указателя начинаются в разных местах. Другие значения r ₂ не имеют этого свойства.

Answer 4

Если быстрый указатель перемещается на 3 шагов и медленный указатель на 1 шаге, то не гарантируется, что оба указателя встретятся в циклах, содержащих четное число узлов. Однако, если медленный указатель перемещается с шагом 2, встреча будет гарантирована.

В общем, , если заяц движется с шагом H, а черепаха с шагом T, вы гарантированно встретитесь в цикле, если H = T + 1.

Рассмотрим, как заяц движется относительно черепахи.

• Скорость зайца по отношению к черепахе составляет H - T узлов за итерацию.

• Дан цикл длины N =(H - T) * k, где k - любое положительное число. целое число, заяц будет пропускать каждые H - T - 1 узлов (опять же, относительно черепахе), и им было бы невозможно встретиться, если бы черепаха была в любом из этих узлов.

• Единственная возможность, когда собрание гарантировано, это когда H - T - 1 = 0.

Следовательно, допустимо увеличение быстрого указателя на x, если медленный указатель увеличен на x - 1.

Answer 5

Если есть цикл (из n узлов), то, как только указатель вошел в цикл, он останется там навсегда; так что мы можем двигаться вперед во времени, пока оба указателя не будут в цикле. С этого момента указатели могут быть представлены целыми числами по модулю n с начальными значениями a и b. Условие для них после t шагов -

a + t≡b + 2t mod n который имеет решение t = a − b mod n.

Это будет работать до тех пор, пока разница между скоростями не делится на простые множители с n.

Ссылка https://math.stackexchange.com/questions/412876/proof-of-the-2-pointer-method-for-finding-a-linked-list-loop

Единственное ограничение скоростей заключается в том, что их разность должна быть равна простой длине цикла.

Answer 6

Если в связанном списке есть цикл, быстрый указатель с шагом 2 будет работать лучше, чем, скажем, шаг 3 или 4 или более, поскольку он гарантирует, что, как только мы окажемся внутри цикла, указатели обязательно столкнутся и не будет обгон.

Например, если мы примем 3 и внутри цикла, допустим,

fast pointer --> i  
slow         --> i+1 
the next iteration
fast pointer --> i+3  
slow         --> i+2

тогда как такой случай никогда не произойдет с шагом 2.

Также, если вам действительно не повезло, вы можете оказаться в ситуации, когда длина цикла равна L, и вы увеличиваете быстрый указатель на L+1. Тогда вы застрянете бесконечно, так как разница движения быстрого и медленного указателя всегда будет L.

Надеюсь, я ясно дал понять.