Время работы таблицы префиксов KMP

Я написал код для заполнения таблицы префиксов для KMP. Это небольшая вариация этого алгоритма. Я не могу убедить себя, что этот алгоритм/реализация выполняется за время O(n). Мне трудно понять, как второй рекурсивный вызов влияет на общее время выполнения. Любая помощь?

    public void fillFailTable(int[] failTable,String p){
        failTable[failTable.length-1] = preLength(failTable,p);
    }

    private int preLength(int[] failTable,String s){

        if(s.length() == 1){
            return 0;
        }
        int n = s.length();
        int k = preLength(failTable,s.substring(0,n-1));

        failTable[n-2] = k;

        if(s.charAt(k) == s.charAt(n-1)){
            return k+1;
        }else{
            return preLength(failTable,s.substring(n-1-k));
        }
    }

java performance algorithm string-matching
person FourOfAKind    schedule 05.08.2012    source источник
comment
Используйте профайлер — посмотрите здесь: pawel-michalski-javnie.blogspot .com/2012/07/jvisualvm.html   -  person dantuch    schedule 06.08.2012

Ответы (1)


arrow_upward
0
arrow_downward

На самом деле это довольно интересно (мне все еще интересно, почему никто умнее меня еще не ответил на этот вопрос). Пожалуйста, отнеситесь к этому объяснению с долей скептицизма, так как я не уверен на 100%, что это даже близко к правильности (хотя я могу сказать вам на 100%, что этот метод работает за O(n), так как это то, что мне сказали в университет много лет назад, но они не удосужились объяснить это, так что мне пришлось придумать это самостоятельно).

Итак, давайте начнем с очень простого примера s.length = 2. Заранее следует упомянуть две вещи:

  • в каждом примере давайте беспокоиться только о наихудшем сценарии, поскольку нас интересует Big Oh, то есть мы вводим второй метод preLength().
  • мы можем наблюдать при поиске большого О, что "k" (и значения, возвращаемые preLength()) в этом коде всегда будут равны 0, что вы заметите на изображениях ниже и что на самом деле важно.

с.длина == 2

Сначала мы вводим первый метод preLength() (назовем его *), который теперь вызывается с s.length = 1 и немедленно возвращается с 0. Теперь, поскольку мы рассматриваем только наихудший сценарий (имеется в виду s.charAt( k) != s.charAt(n-1)) мы вводим вторую preLength() также со строкой длины = 1 (поскольку n=2 и k=0). Этот также немедленно возвращает 0 в наш файл *. На этом вызов нашего метода заканчивается. Всего у нас было 3 вызова метода. Наш * и два preLength(). Вот изображение:

введите здесь описание изображения

с.длина == 3

Теперь давайте посмотрим на пример с начальным значением s.length = 3. Как вы можете заметить, мы немедленно вызываем preLength() с s.length = 2, и из нашего предыдущего примера мы знаем, что для этого требуется 3 вызова метода. Теперь нам нужно помнить, что когда метод preLength(2) возвращается на этот раз, он возвращается к нашему собственному preLength(3), который теперь снова вызовет preLength(2) (тот, что в else), для которого снова потребуется 3 вызова метода. Итак, всего нам нужно 2*3+1 вызова метода. Это дает нам 7. Опять же, вот изображение (круг — это вызов preLength со строкой длины, показанной в круге):

введите здесь описание изображения

Выводы

Теперь, как вы можете видеть, все эти вызовы методов симметричны, и это потому, что наш k всегда равен 0, что означает, что второй preLengt() будет вызываться со строкой того же размера, что и первый - и мы можем увидеть, сколько из них нам понадобится для s.length = m, когда мы знаем, сколько из них нам нужно для m-1, поскольку f(m) = 2*f(m-1)+1, где f(m) - это функция, сообщающая нам, сколько вызовов метода нам нужно, чтобы вычислить таблицу для строки размер m. Это работает, поскольку, как я уже говорил, вызовы методов симметричны (это потому, что в худшем случае k=0 всегда и preLenght() всегда возвращает 0, следовательно, 2* и нам нужно добавить 1 вызов метода, первый, который мы когда-либо вызывали).

Таким образом, в основном с каждым увеличением нашего ввода (размер m) время вычислений увеличивается в 2 раза плюс один (2 * m + 1), что, насколько я понимаю, означает, что этот метод в худшем случае O (n).

Как я уже сказал, пожалуйста, отнеситесь к этому с недоверием, но я надеюсь, что это имеет какой-то смысл :)

person Mateusz Dymczyk    schedule 05.08.2012