Почему функция отказа KMP может быть вычислена за время O (n)?
Википедия утверждает что таблица функции отказа может быть вычислена за время 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 — длина искомого шаблона.