Време на работа на таблицата с префикси на 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
Използвайте Profiler - тук, погледнете: 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().
  • можем да наблюдаваме, когато търсим Big Oh, че "k" (и стойностите, върнати от preLength()) в този код винаги ще бъде 0, което ще забележите в изображенията по-долу и което е наистина важно.

s.length == 2

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

въведете описание на изображението тук

s.length == 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