英文:
Summation of time complexity Brute force string match computation
问题
I am trying to solve the summation computation of the time complexity of brute force string match.
The algorithm is:
for (int i = 0; i < n-m; i++) {
int j = 0;
while (j < m && t[i+j] == p[j]) {
j++;
}
if (j == m) return i;
}
System.out.println(‘‘Element not found.’’);
return -1;
I have attached my unfinished computation and still trying to solve it. Can someone tell me if I am doing it correctly or wrong? Should I continue getting the answer on the way I solve it? I apologize asking but I am really having a hard time to solve this.
英文:
I am trying to solve the summation computation of the time complexity of brute force string match.
The algorithm is:
for (int i = 0; i < n-m; i++) {
int j = 0;
while (j < m && t[i+j] == p[j]) {
j++;
}
if (j == m) return i;
}
System.out.println(‘‘Element not found.’’);
return -1;
I have attached my unfinished computation and still trying to solve it. Can someone tell me if I am doing it correctly or wrong? Should I continue getting the answer on the way I solve it? I apologize asking but I am really having a hard time to solve this.
答案1
得分: 1
你可以将计算分成以下步骤：
1- for循环从i = 0迭代到i < n - m，每次迭代增加1。这个循环运行(n - m)次。
2- 在for循环内部，有一个while循环，它运行直到j < m且条件t[i+j] == p[j]满足。在最坏的情况下，即没有匹配时，while循环将运行m次。
3- 条件if (j == m)检查是否已经完全匹配了整个模式p。如果是这样，函数将返回当前的i值；否则，它继续到下一个for循环的迭代。
4- 如果for循环在没有找到匹配的情况下完成，代码会打印"Element not found"并返回-1。
在最坏的情况下，该算法将在for循环中迭代(n - m)次，每次迭代中while循环将运行m次。因此，代码的总时间复杂度为O((n - m) * m)。
在情况m << n下，时间复杂度可以近似为O(n*m)。
英文:
You can break your calculation into the following steps:
1- The for loop iterates from i = 0 to i < n - m, incrementing i by 1 in each iteration. This loop runs (n - m) times.
2- Inside the for loop, there is a while loop that runs until j < m and the condition t[i+j] == p[j] is satisfied. In the worst case where there is no match, the while loop will run m times.
3- The condition if (j == m) checks if the entire pattern p has been matched. If so, the function returns the current value of i; otherwise, it continues to the next iteration of the for loop.
4- If the for loop completes without finding a match, the code prints "Element not found" and returns -1.
In the worst case scenario, the algorithm will iterate (n - m) times in the for loop, and in each iteration, the while loop will run m times. Therefore, the overall time complexity of the code is O((n - m) * m).
In the case m << n time complexity can be approximated to O(n*m).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论