0

我在我的程序中实现了 KMP 模式搜索算法来搜索对象表。我想知道如何评估我的功能的时间效率。

我读了一些资料，说 KMP 算法的时间复杂度是O(n) [不包括空间复杂度]

因此，我将遍历从 1 到 N 项的对象列表，在每个项中搜索模式匹配。一旦有比赛，我就会跳出循环，但这并不会真正影响我的评估（我认为）。

因此，由于我迭代了所有项目，所以我的大 O 表示法是：O(n^2)，因为它需要O(n)才能找到匹配项，而O(n)需要遍历我的所有项目。

这是我的一些见解的代码：

while(itr.hasNext()){
    //M is the length of our pattern

    i = 0; //index of text to be searched
    j = 0; //index of our pattern

    txt  = itr.next().toString();  //Store the key inside txt string
    N = txt.length(); //length of our text to be search
    
    //Check if the searchText is equal or less than key in the dictionary
    //If our searchText is more than the key length, there is no use of searching
    if(M <= N){
        while (i < N) {
            //Check if the searchText.charAt equals to txt.charAt
            //Increase i,j if matches to compare next character(s)
            if (searchText.charAt(j) == txt.charAt(i)) { 
                j++; 
                i++; 
            }else{ //If the chars at our pattern and text does not match
                if (j != 0) //if it's not the first index of our pattern
                    j--; //reduce one index
                else
                    i++; //otherwise move onto the next index of our text to be searched
            }
            
            //Check whether the length of the searchText equals to the match counter
            //It means that the searchKey exists in our dictionary
            if (j == M) { 
                System.out.println((String.format("%-35s", txt)) + get((K)txt));
                counter++;      //Holds the number of entries found
                j--; 
                break;          //No need to look anymore since there's a match
            }
        }
    }
}
4

1 回答 1

0

如果您的列表中有 n 个项目并且平均每个元素大小为 m，那么搜索时间复杂度将为 O(mn)。对于每个元素，KMP 的搜索时间复杂度为 O(m)。您需要将其乘以 n。

于 2020-09-12T09:28:58.860 回答