Złożoność naiwnego algorytmu znajdowania najdłuższego substratu Fibonacciego

Biorąc pod uwagę dwa symbole i b , niech określić k -tego ciąg Fibonacciego, co następuje:$\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}$$

z oznaczającym konkatenację łańcucha.$\star$

W ten sposób będziemy mieli:

• $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}$
• ...

Biorąc pod uwagę ciąg tworzą n symboli określamy Fibonacciego podciągu za każdym fragmentu z S , który jest również ciąg Fibonacciego odpowiedniego wyboru i b .$S$$n$$S$$\text{a}$$\text{b}$

Problem

Biorąc pod uwagę literę , chcemy znaleźć jej najdłuższy substrat Fibonacciego.$S$

Trywialny algorytm

Dla każdej pozycji ciągu S załóżmy, że zaczyna się F ( 2 ) (wystarczy sprawdzić, czy symbole i- ty i ( i + 1 ) -ty są różne). W takim przypadku sprawdź, czy można go rozszerzyć na F ( 3 ) , a następnie F ( 4 ) i tak dalej. Następnie zacznij ponownie od pozycji i + 1 . Powtarzaj, aż dojdziesz do pozycji n .$i$$S$$F(2)$$i$$(i+1)$$F(3)$$F(4)$$i+1$$n$

Musimy spojrzeć na każdy symbol przynajmniej raz, więc jest to . W grę wchodzą tylko dwie pętle, więc możemy ponadto powiedzieć, że jest to O ( n 2 ) .$\Omega(n)$$O(n^2)$

Jednak (nieco zaskakujące) ten naiwny algorytm działa znacznie lepiej niż zwykle algorytmy kwadratowe (jeśli wykonuje dużo pracy na tej pozycji, nie wykona dużo pracy na następnych pozycjach).$i$

Jak mogę użyć właściwości Fibonacciego, aby znaleźć ściślejsze granice dla czasu wykonywania tego algorytmu?

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