Arquivo da categoria: implementação

Implementação – Fast Doubling

Descobrir o n-ésimo elemento da sequência de fibonacci é o problema mais manjado de competições de programação, mas mesmo assim sempre há uma forma criativa de expor esse conceito e por isso é bom estar preparado.

Se você só conhece o método recursivo e/ou iterativo (O(n)), uma hora ou outra vai passar algum apuro para descobrir alguns valores maiores.

Por mais que essa sequência seja um grande mistério, e ainda não se conhece uma fórmula* 100% precisa para descobrir os elementos, para nossa salvação há alguns métodos com complexidade bem “amigáveis”.

Clique no link abaixo para ver a implementação do algoritmo Fast Doubling, que descobre o n-ésimo elemento em complexidade O(log N).
Continue lendo Implementação – Fast Doubling