Когда алгоритм поиска циклов Флойда потерпит неудачу?
Я получаю интервью на вопрос о Алгоритм обнаружения циклов Флойда :
Когда алгоритм поиска циклов Флойда потерпит неудачу?
Я имею в виду, есть ли правило для нахождения шага между быстрым и медленным указателями?
Решение
При разумных предположениях это не подведет. Он либо найдет цикл, либо заключит, что его нет.
Единственные сценарии сбоя, которые я могу придумать, имеют следующие черты:
- в реализации есть ошибка;
- пересекаемая структура модифицируется во время работы алгоритма.
Другие решения
Там может быть никаких возможных ситуаций сбоя для алгоритма поиска цикла Флойда.
Единственный возможный сценарий сбоя возникает, когда в вычислительном отношении трудно найти следующий узел в динамически изменяющемся связанном списке.