Википедия утверждает что таблица функции отказа может быть вычислена за время O (n).
Давайте посмотрим на его «каноническую» реализацию (в C ++):
vector<int> prefix_function (string s) {
int n = (int) s.length();
vector<int> pi (n);
for (int i=1; i<n; ++i) {
int j = pi[i-1];
while (j > 0 && s[i] != s[j])
j = pi[j-1];
if (s[i] == s[j]) ++j;
pi[i] = j;
}
return pi;
}
Почему он работает за O (n), даже если есть внутренний цикл while? Я не очень силен в анализе алгоритмов, так может кто-нибудь объяснить это?
Эта строка: if (s [i] == s [j]) ++ j; выполняется не более O (n) раз.
Это вызвало увеличение значения p [i]. Обратите внимание, что p [i] начинается с того же значения, что и p [i-1].
Теперь эта строка: j = pi [j-1]; вызывает уменьшение p [i] как минимум на единицу. А поскольку он был увеличен не более чем в O (n) раз (мы считаем также, увеличивается и уменьшается по предыдущим значениям), его нельзя уменьшить более, чем в O (n) раз.
Так что это также выполняется не более O (n) раз.
Таким образом, сложность всего времени равна O (n).
Здесь уже есть два правильных ответа, но я часто думаю, что
доказательства могут прояснить ситуацию. Вы сказали, что хотите получить ответ для 9-летнего ребенка, но
Я не думаю, что это возможно (я думаю, что это легко обмануть себя думать, что это правда
фактически не имея никакой интуиции, почему это так). Возможно, проработка этого ответа поможет.
Во-первых, внешний цикл работает n
раз ясно, потому что i
не модифицируется
в цикле. Единственный код в цикле, который может выполняться более одного раза,
блок
while (j > 0 && s[i] != s[j])
{
j = pi[j-1]
}
Так сколько раз это может бежать? Хорошо заметьте, что каждый раз, когда это условие
удовлетворены, мы уменьшаем ценность j
который на данный момент, самое большее
pi[i-1]
, Если оно достигает 0, то while
цикл сделан. Чтобы понять, почему это важно,
мы сначала докажем лемму (вы очень умный 9-летний):
pi[i] <= i
Это сделано по индукции. pi[0] <= 0
так как он установлен один раз при инициализации pi
и никогда не трогал снова. Тогда индуктивно мы позволяем 0 < k < n
и предположим
иск распространяется на 0 <= a < k
, Учитывайте ценность p[k]
, Это установлено
точно один раз в очереди pi[i] = j
, Ну как большой может j
быть? Это инициализировано
в pi[k-1] <= k-1
по индукции. В блоке while он может быть обновлен до pi[j-1] <= j-1 < pi[k-1]
, По другой мини-индукции вы можете видеть, что j
никогда не пройдёт мимо pi[k-1]
, Следовательно, после
while
цикл у нас еще есть j <= k-1
, Наконец, это может быть увеличено один раз, поэтому мы имеем
j <= k
так что pi[k] = j <= k
(это то, что нам нужно было доказать, чтобы закончить нашу индукцию).
Теперь, возвращаясь к исходной точке, мы спрашиваем: «Сколько раз мы можем уменьшить значение
j
«Хорошо с нашей леммой теперь мы можем видеть, что каждая итерация while
цикл будет
монотонно уменьшить значение j
, В частности мы имеем:
pi[j-1] <= j-1 < j
Так сколько раз это можно запустить? В большинстве pi[i-1]
раз. Проницательный читатель может подумать
«Вы ничего не доказали! У нас есть pi[i-1] <= i-1
но это внутри цикла, так
это все еще O(n^2)
! «. Немного более проницательный читатель замечает этот дополнительный факт:
Однако много раз мы бежим
j = pi[j-1]
затем мы уменьшаем значениеpi[i]
что сокращает следующую итерацию цикла!
Например, скажем, j = pi[i-1] = 10
, Но после ~ 6 итераций while
петля у нас есть
j = 3
и скажем, он увеличивается на 1 в s[i] == s[j]
линия так j = 4 = pi[i]
,
Ну тогда на следующей итерации внешнего цикла мы начнем с j = 4
… так что мы можем только выполнить while
максимум 4 раза.
Последняя часть головоломки состоит в том, что ++j
работает не более одного раза за цикл. Так что это не так, как мы можем иметь
как то так в нашем pi
вектор:
0 1 2 3 4 5 1 6 1 7 1 8 1 9 1
^ ^ ^ ^ ^
Those spots might mean multiple iterations of the while loop if this
could happen
Чтобы сделать это действительно формальным, вы можете установить инварианты, описанные выше, а затем использовать индукцию
чтобы показать, что Всего сколько раз while
цикл запускается, суммируется с pi[i]
самое большее i
,
Из этого следует, что Всего количество раз while
цикл запускается O(n)
это означает, что весь внешний цикл имеет сложность:
O(n) // from the rest of the outer loop excluding the while loop
+ O(n) // from the while loop
=> O(n)
Давайте начнем с того факта, что внешний цикл выполняется n раз, где n — длина искомого шаблона. Внутренний цикл уменьшает значение j
по крайней мере 1, так как pi[j] < j
, Цикл заканчивается не позднее, когда j == -1
следовательно, это может уменьшить значение j
самое большее, как это было ранее увеличено j++
(внешний цикл). поскольку j++
выполняется во внешнем цикле точно n
время, общее количество выполнений внутреннего цикла while ограничено n
, Следовательно, алгоритм предварительной обработки требует O (n) шагов.
Если вам это интересно, рассмотрите эту более простую реализацию этапа предварительной обработки:
/* ff stands for 'failure function': */
void kmp_table(const char *needle, int *ff, size_t nff)
{
int pos = 2, cnd = 0;
if (nff > 1){
ff[0] = -1;
ff[1] = 0;
} else {
ff[0] = -1;
}
while (pos < nff) {
if (needle[pos - 1] == needle[cnd]) {
ff[pos++] = ++cnd;
} else if (cnd > 0) {
cnd = ff[cnd]; /* This is O(1) for the reasons above. */
} else {
ff[pos++] = 0;
}
}
}
из которого совершенно очевидно, что функция отказа — это O (n), где n — длина искомого шаблона.