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

Ответ 1

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

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

Здесь теорема, которая делает алгоритм Флойда:

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

Пусть это докажет это; это не так сложно. Для случая "if", если такой j существует, выберите k = 2. Тогда мы получим, что для некоторого положительного j х _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 будет не более 2s, поэтому значение j равно O (s + l). Так как l и s могут быть не больше числа элементов в списке, это означает, что j = O (n). Однако после того, как медленный указатель выполнил j шагов, быстрый указатель выполнил k шагов для каждого из шагов j, выполняемых медленным указателем, чтобы он выполнил шаги O (kj). Поскольку j = O (n), чистое время выполнения не более O (nk). Обратите внимание, что это говорит о том, что чем больше шагов мы предпринимаем с быстрым указателем, тем дольше алгоритм берется до конца (хотя только пропорционально). Таким образом, выбор k = 2 сводит к минимуму общую продолжительность выполнения алгоритма.

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

Ответ 2

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

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

Итак, расстояние медленного указателя перемещается = s + j. Расстояние быстрого перемещения указателя = s + j + m * t. Но быстрая указатель также пройла бы расстояние 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, больше расстояние, на которое должны были бы двигаться два указателя.

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

Ответ 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. После того, как еще один указатель указателя увеличивается, первый указатель находится в x _{k + (m mod L)}, а второй указатель находится в x _{k + ((m * r 2 + s) mod L)}. Поэтому условие столкновения двух указателей можно сформулировать как существование т, удовлетворяющее конгруэнции

m = m * r ₂ + s (mod L)

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

m (1-r ₂) = s (mod L)

m (L + 1-r ₂) = s (mod 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 ₂ не имеют этого свойства.

Ответ 4

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

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

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

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

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

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

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

Ответ 5

Если связанный список имеет цикл, то быстрый указатель с шагом 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.

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