Complejidad de un algoritmo ingenuo para encontrar la subcadena de Fibonacci más larga

Dados dos símbolos y , definamos la -ésima cadena de Fibonacci de la siguiente manera:b $\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}$$

con denotando concatenación de cadenas.$\star$

Así tendremos:

• $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 una cadena formada por n símbolos, definimos una subcadena de Fibonacci como cualquier subcadena de S que también es una cadena de Fibonacci para una elección adecuada de a y b .$S$$n$$S$$\text{a}$$\text{b}$

El problema

Dado , queremos encontrar su subcadena de Fibonacci más larga.$S$

Un algoritmo trivial

Para cada posición de la cadena S , suponga que F ( 2 ) comienza allí (es suficiente para verificar que los símbolos i -th e ( i + 1 ) -th son distintos). Si ese es el caso, verifique si se puede extender a F ( 3 ) , luego a F ( 4 ) , y así sucesivamente. Después de eso, comience nuevamente desde la posición i + 1 . Repita hasta llegar a la posición n .$i$$S$$F(2)$$i$$(i+1)$$F(3)$$F(4)$$i+1$$n$

Debemos mirar cada símbolo al menos una vez, por lo que es . Solo hay dos para los bucles involucrados, por lo que además podemos decir que es O ( n 2 ) .$\Omega(n)$$O(n^2)$

Sin embargo (como era de esperar), este ingenuo algoritmo funciona mucho mejor que los algoritmos cuadráticos habituales (si hace mucho trabajo en la posición -ésima, no hará mucho trabajo en las siguientes posiciones).$i$

¿Cómo puedo usar las propiedades de Fibonacci para encontrar límites más ajustados para el tiempo de ejecución de este algoritmo?

Digamos que ocurre en alguna posición si la subcadena que comienza en esa posición es compatible con F ( n ) o su complementación. ¿Qué tan cerca pueden estar las ocurrencias de F ( n ) ? Tome como ejemplo F ( 4 ) = a b a a b . Si F ( 4 ) ocurre en la posición p, entonces no puede ocurrir en la posición p + 1 o p + $F(n)$ $F(n)$$F(n)$$F(4) = abaab$$F(4)$$p$$p+1$$p+2$, pero puede aparecer en la posición . Dejamos que ℓ ( n ) sea ​​el número más pequeño, de modo que dos ocurrencias de F ( ℓ ) pueden ocurrir a una distancia de ℓ . Puede probar por inducción que para n ≥ 4 tenemos ℓ ( n ) = | F ( n - 1 ) | (por ejemplo, ℓ ( 4 ) = 3 ).$p+3$$\ell(n)$$F(\ell)$$\ell$$n \geq 4$$\ell(n) = |F(n-1)|$$\ell(4) = 3$

Dada una cadena de longitud , para cada n sea P ( n ) el conjunto de posiciones en las que se produce F ( n ) . Podemos limitar el tiempo de ejecución de su procedimiento aproximadamente por ∑ n | P ( n ) | El | F ( n ) | , donde la suma se ejecuta sobre todos n tal que | F ( n - 1 ) | ≤ N (decir). Como ocurrencias de F ( $N$$n$$P(n)$$F(n)$$\sum_n |P(n)| |F(n)|$$n$$|F(n-1)| \leq N$ están separados por al menos | F ( n - 1 ) | , vemos que el tiempo de ejecución está limitado por el orden de ∑ n | F ( n ) | ( $F(n)$$|F(n-1)|$ Como las longitudes de las palabras de Fibonacci aumentan exponencialmente,∑n| F(n)| =O(N). El término restante es∑nO(N)=O(NlogN), ya que la suma contienelogNmuchos términos. Concluimos que el tiempo de ejecución esO(Nlog

$$\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)$

Por el contrario, el tiempo de ejecución en es Ω ( | F n | log | F n | ) , como puede probarse por inducción. Llegamos a la conclusión de que el peor tiempo de ejecución en cadenas de longitud N es Θ ( N log N ) .$F_n$$\Omega(|F_n|\log|F_n|)$$N$$\Theta(N\log N)$