Сложность наивного алгоритма нахождения самой длинной подстроки Фибоначчи

Учитывая два символа и , давайте определим строку Фибоначчи следующим образом: $\text{a}$ $\text{b}$ $k$

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

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

с обозначающей конкатенацию строк. $\star$

Таким образом, мы будем иметь:

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

Получая строку , образованный символов, определим Фибоначчи подстроки как любой подстроки из , которая также является строкой Фибоначчи для подходящего выбора и . $S$ $n$ $S$ $\text{a}$ $\text{b}$

Проблема

Учитывая , мы хотим найти его самую длинную подстроку Фибоначчи. $S$

Тривиальный алгоритм

Для каждой позиции строки предположим, что там начинается (достаточно проверить, что и -й символы различны). Если это так, проверьте, можно ли его расширить до , затем и т. Д. После этого начните снова с позиции . Повторяйте, пока не достигнете позиции . $i$ $S$ $F(2)$ $i$ $(i+1)$ $F(3)$ $F(4)$ $i+1$ $n$

Мы должны посмотреть на каждый символ хотя бы один раз, так что это . Здесь задействованы только два цикла for, поэтому мы можем также сказать, что это . $\Omega(n)$ $O(n^2)$

Однако (что неудивительно) этот наивный алгоритм работает намного лучше, чем обычные квадратичные алгоритмы (если он выполняет большую работу на позиции, он не будет выполнять большую работу на следующих позициях). $i$

Как я могу использовать свойства Фибоначчи, чтобы найти более точные границы для времени выполнения этого алгоритма?

algorithms algorithm-analysis runtime-analysis strings substrings wil93
источник

Ответы:

Скажем, что встречается в некоторой позиции, если подстрока, начинающаяся в этой позиции, совместима либо с либо с ее дополнением. Насколько близко могут быть вхождения ? Возьмите в качестве примера . Если возникает в позиции то она не может появляться в позиции или , но она может появляться в позиции . Мы допустим наименьшее число, такое, что два вхождения могут произойти на расстоянии . Вы можете по индукции доказать, что для имеем $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) | (\frac{N}{| F (n - 1) |} + 1) .

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

\sum_{n} | F (n) | = O (N)

$\sum_n |F(n)| = O(N)$

\sum_{n} O (N) = O (N \log N)

$\sum_n O(N) = O(N\log N)$ , так как сумма содержит много членов. Мы заключаем, что время выполнения .

\log N

$\log N$

O (N \log N)

$O(N\log N)$

Наоборот, время выполнения на равно , что можно доказать по индукции. Мы заключаем, что наихудшее время выполнения для строк длины - это . $F_n$ $\Omega(|F_n|\log|F_n|)$ $N$ $\Theta(N\log N)$

Юваль Фильмус
источник