朴素算法实现

Question

为什么朴素算法的时间复杂度不能为o(n)？这是我的Java代码，它给了我预期的结果。请解释一下这是怎么回事。

import java.util.*;
class NaiveAlgo{
    public static void main (String args[]){
        System.out.print("Enter the Text : ");
        Scanner inp1=new Scanner(System.in);
        String txt=inp1.nextLine();
        int lengthT=txt.length();

        System.out.print("Enter the Pattern : ");
        Scanner inp2=new Scanner(System.in);
        String ptn=inp2.nextLine();
        int lengthP=ptn.length();

        int i=0,j=0,index=0;

        while(j!=lengthP&& i!=lengthT){
            if(txt.charAt(i)==ptn.charAt(j)){
              i++;
              j++;
            }else{
              j=0;
              index++;
              i=index;
            }
        }

    if(index<lengthT)
            System.out.println("Index : "+index);
    else
            System.out.println("Not found ");
    }
}

Answer 1

你的算法复杂度不是O(n)。它没有执行线性搜索--这是在字符不匹配时重置j=0和i=index时发生的。

假设ptn=xxxxy和txt=xxxxxxxxxxxxxxxxxxxxy的输入过于夸张，那么它的效率将不会很高，我相信这会导致O(nm)。算法中的逻辑复位ptn的计数器，并且仅将txt的索引递增1。

您可以将您的执行与Boyer–Moore子串搜索算法进行比较，并查看它与您的算法有何不同：

https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm