Complexidade de um algoritmo ingênuo para encontrar o substring de Fibonacci mais longo

Dado dois símbolos e b , vamos definir o k -ésimo seqüência de Fibonacci da seguinte forma:$\text{a}$$\text{b}$$k$

$$F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\ \text{a} &\mbox{if } k = 1 \\ F(k-1) \star F(k-2) &\mbox{else} \end{cases}$$

com denotando concatenação de strings.$\star$

Assim, teremos:

• $F(0) = \text{b}$
• $F(1) = \text{a}$
• $F(2) = F(1) \star F(0) = \text{ab}$
• $F(3) = F(2) \star F(1) = \text{aba}$
• $F(4) = F(3) \star F(2) = \text{abaab}$
• ...

Dada uma sequência formada por n símbolos, definimos uma substring de Fibonacci como qualquer substring de S, que também é uma sequência de Fibonacci para uma escolha adequada de a e b .$S$$n$$S$$\text{a}$$\text{b}$

O problema

Dado , queremos encontrar o substring Fibonacci mais longo.$S$

Um algoritmo trivial

Para cada posição da string S , suponha que F ( 2 ) comece aí (basta verificar se os símbolos i -ésimo e ( i + 1 ) -ésimo são distintos). Se for esse o caso, verifique se pode ser estendido para F ( 3 ) , depois F ( 4 ) e assim por diante. Depois disso, comece novamente a partir da posição i + 1 . Repita até chegar à posição n .$i$$S$$F(2)$$i$$(i+1)$$F(3)$$F(4)$$i+1$$n$

Devemos olhar para cada símbolo pelo menos uma vez, então é . Existem apenas dois para loops envolvidos, então podemos dizer que é O ( n 2 ) .$\Omega(n)$$O(n^2)$

No entanto (de maneira não surpreendente), esse algoritmo ingênuo tem desempenho quadrático muito melhor que o usual (se fizer muito trabalho na ésima posição, não fará muito trabalho nas próximas posições).$i$

Como posso usar as propriedades de Fibonacci para encontrar limites mais apertados para o tempo de execução desse algoritmo?

$F(n)$ $F(n)$$F(n)$$F(4) = abaab$$F(4)$$p$$p+1$$p+2$$p+3$$\ell(n)$$F(\ell)$$\ell$$n \geq 4$$\ell(n) = |F(n-1)|$$\ell(4) = 3$

$N$$n$$P(n)$$F(n)$$\sum_n |P(n)| |F(n)|$$n$$|F(n-1)| \leq N$$F(n)$$|F(n-1)|$

$$\sum_n |F(n)| \left(\frac{N}{|F(n-1)|} + 1\right).$$ $\sum_n |F(n)| = O(N)$$\sum_n O(N) = O(N\log N)$$\log N$$O(N\log N)$

$F_n$$\Omega(|F_n|\log|F_n|)$$N$$\Theta(N\log N)$