Оптимальная скорость быстрого указателя в алгоритме Флойда для определения цикла

Из ответа CEGRD (Объясните, как работает поиск начального узла цикла в связанном списке циклов?) мы можем видеть, что если скорость быстрого указателя равна c, то скорость медленного указателя должна соответствовать следующим критериям:
я: длина покрыта медленным указателем
m: расстояние от начала связанного списка до начала цикла
n: длина цикла
k: расстояние от начала цикла до текущего узла (

i = m + p*n + k
c*i = m + q*n + k
=> m + k = n(q - p*c)/(c-1);

теперь мы должны минимизировать i, что сводится к i = n (b-a) / c-1;
=> c должно быть большим, чтобы минимизировать i, следовательно, c = 2 не является оптимальным значением, c должно быть большим.
Пожалуйста помоги.

0

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]