- 我想知道这在最坏的情况下是否有效,如
Θ(n+m)
?
n
是i_StringForSearch
的大小,m
是i_SubStringToFind
的大小。
2.是否有推荐的程序来检查给定代码的时间复杂度,我更喜欢公认的免费工具。
谢谢
public static boolean isSubstring(String i_StringForSearch, String i_SubStringToFind)
{
int strForSearchIndex = 0;
int subStrToFindIndex = 0;
boolean endOfStringToSearch = false;
boolean foundSubString = false;
boolean isThereASequenceOfMatching = false;
while(!endOfStringToSearch && !foundSubString)
{
if(strForSearchIndex == i_StringForSearch.length())
{
endOfStringToSearch = true;
}
else if(i_StringForSearch.charAt(strForSearchIndex) == i_SubStringToFind.charAt(subStrToFindIndex))
{
isThereASequenceOfMatching = true;
if(subStrToFindIndex == i_SubStringToFind.length() -1 )
{
foundSubString = true;
}
subStrToFindIndex++;
strForSearchIndex++;
}
else if(i_StringForSearch.charAt(strForSearchIndex) != i_SubStringToFind.charAt(subStrToFindIndex))
{
if(isThereASequenceOfMatching)
{
subStrToFindIndex = 0;
isThereASequenceOfMatching = false;
}
strForSearchIndex++;
}
}
return foundSubString;
}
最佳答案
回答你的问题:是的,算法是
O(n+m)
。每个 迭代增加strForSearchIndex
,所以最多有n
迭代。 [这是假设i_StringForSearch.length()
完成 在O(1)
中,这通常是正确的。isSubstring("aaab","aab") == false
的反例算法错误你可能想看看 Knuth Morris Pratt algorithm和/或 Rabin-Karp algorithm和/或 Aho-Corasick Algorithm
关于时间复杂度的算法回顾,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12261806/