Почему функция отказа KMP вычисляется в O (n) времени?

Ответ 1

Эта строка: 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).

Ответ 2

Здесь уже два ответа, которые правильны, но я часто думаю, что полностью выложены доказательство может сделать вещи более ясными. Вы сказали, что хотите ответить 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, но внутри цикла while это еще 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 vector:

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) 

Ответ 3

Начнем с того, что внешний цикл выполняет 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 - длина искомого образца.