Нахождение цикла
алгоритмическая задача / Материал из Википедии — свободной encyclopedia
Уважаемый Wikiwand AI, давайте упростим задачу, просто ответив на эти ключевые вопросы:
Перечислите основные факты и статистические данные о Алгоритм Флойда поиска длины цикла?
Кратко изложите эту статью для 10-летнего ребёнка
Нахождение цикла — алгоритмическая задача поиска цикла в последовательности значений итеративной функции[англ.].
Для любой функции f, отображающей конечное множество S в себя, и для любого начального значения x0 из S последовательность итеративных значений функции:
должна в конечном счёте использовать одно значение дважды, то есть должна существовать такая пара индексов i и j, что xi = xj. Как только это случится, последовательность будет продолжаться периодически, повторяя ту же самую последовательность значений от xi до xj − 1. Нахождение цикла — это задача поиска индексов i и j при заданной функции f и начальном значении x0.
Известно несколько алгоритмов поиска цикла быстро и при малой памяти. Алгоритм «черепахи и зайца» Флойда передвигает два указателя с различной скоростью через последовательность значений, пока не получит одинаковые значения. Другой алгоритм, алгоритм Брента, основан на идее экспоненциального поиска[англ.]. Оба алгоритма, Флойда и Брента, используют только фиксированное число ячеек памяти, и число вычислений функции пропорционально расстоянию от стартовой точки до первой точки повторения. Некоторые другие алгоритмы используют большее количество памяти, чтобы получить меньшее число вычислений значений функции.
Задача нахождения цикла используется для проверки качества генераторов псевдослучайных чисел и криптографических хеш-функций, в алгоритмах вычислительной теории чисел[англ.], для определения бесконечных циклов в компьютерных программах и периодических конфигураций клеточных автоматов, а также для автоматического анализа формы[англ.] связных списков.