Mostrar código-fonte de Algoritmo busca-ciclos de Floyd

'''Algoritmo para Busca de Ciclos de Floyd''' é um [[algoritmo]] inventado por [[Robert W. Floyd]] em 1967 para  detectar ciclos em sequências arbitrárias, seja em estruturas de dados ou geradas ao vivo (especialmente  grafos e [[seqüência|sequência]]s [[pseudo-aleatória]]s) usando espaço [[O]](1). Algumas vezes este algoritmo é chamado de algoritmo-"tartaruga e a lebre".

A discussão a seguir é construída em termos de sequências aleatórias em particular, de grande importância na análise de geradores de número pseudo-aleatórios e nas aplicações de algoritmos  tais como fatoração o [[algoritmo rho de Pollard]].

Seja

:<math>f\colon S\mapsto S</math>

uma [[função (matemática)|função]] pseudo-aleatória, com ''S'' um conjunto de cardinalidade finita ''n''. Define-se uma seqüência ''a''<sub>''i''</sub> como:
<center>
:<math>a_{i+1}=f(a_i)</math>
</center>
Evidentemente tal seqüência deve ter um ciclo após pelo menos ''n'' interações da função pseudo-aleatória, porque há somente n possíveis valores para um elemento. A maneira de naïve para encontrar o tamanho deste ciclo é guardar cada elemento da seqüência e, após cada iteração, procurar entre todos eles por duplicações. Isto significa que a necessidade de armazenamento é  O(μ + λ), onde μ é o tamanho do ciclo e λ é o tamanho da cauda (isto é, da parte da seqüência que não é cíclica).

Note que se nos encontramos dois elementos de seqüência tal que
:<math>a_i=a_{j}</math>

então |''i'' − ''j''| deve ser múltiplo do comprimento do ciclo, porque a definição de uma seqüência cíclica é:

:<math>a_{\lambda+m}=a_{\lambda+m+k\mu}.</math>

A diferença entre os dois índices que armazenam elementos iguais é ''k''μ, um múltiplo do comprimento do ciclo. Algoritmo de busca-cíclica de Floyd encontra tal igualdade pelo processamento de duas instâncias de sequências em paralelo, uma das quais é mais "rápida" do que a outra; isto é uma instância processa duas iterações enquanto a outra processa uma. Então, quando:

:<math>a_m=a_{2m}</math>

então qualquer divisor de 2''m'' − ''m'' = ''m'' deve ser o comprimento do ciclo. Se ''m'' é composto, pode-se deixar o algoritmo continuar a processar até que ele encontre mais valores de ''m'' para os quais a igualdade acima é verdadeira, e obter o [[maior divisor comum]] de ''m''. Neste processo, a lista de possíveis μ's pode ser preparada.

[[Ficheiro:CycleFindingNew.png|right|thumb|233 px|Algoritmo Busca-Cíclica de Floyd]] A melhor maneira de visualizar este algoritmo é construir um diagrama da seqüência. Ele se parecerá com a letra Grega [[Rho|&rho;]]. A seqüência inicia-se no fim da cauda, e move-=se para cima girando na direção oposta aos ponteiros do relógio. Acompanhando o algoritmo, as duas instâncias da seqüência irão se encontrar em ''a''<sub>6</sub> depois de 6 iterações. Se o algoritmo continuar, as sequências se encontram novamente, após outras seis iterações, no mesmo elemento. Desde que o comprimento do ciclo seja de fato 6, o mesmo resultado continuará ocorrendo.

No melhor caso, este algoritmo necessita λ comparações (com λ &gt; 1), desde que a seqüência mais lenta tenha de percorrer ao menos a parte inicial do ciclo. O pior caso necessita λ + μ/2 comparações; a seqüência lenta não alcançará mais do que a metade do círculo sem que encontrar a seqüência rápida. O algoritmo usa um armazenamento de O(1).

Talvez a mais difundida variante deste algoritmo seja o [[algoritmo rho de Pollard]], um algoritmo de [[fatoração inteira]] que usa números pseudo-aleatórios para fatorar inteiros. Há também um algoritmo para cálculo de [[logaritmo discreto]]s baseado no Algoritmo de busca-cíclica de Floyd.

{{Esboço-matemática}}

{{DEFAULTSORT:Algoritmo Busca-Ciclica Floyd}}
[[Categoria:Algoritmos]]
[[Categoria:Combinatória]]