java - 天真的算法实现

Question

为什么 Naive 算法不能有 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 和 txx=xxxxxxxxxxxxxxxxxxxxy 的夸张的最坏情况输入，它不会有效，这将导致它是 O(nm)我相信。算法中的逻辑为 ptn 重置计数器，并且仅将 txt 的索引递增 1。

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

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