英文:
What is the BigO notation on searching on a string that keeps changing for a character
问题
以下是您要翻译的内容：
我有下面的函数，它在一个字符串中查找最长的不重复子字符串。
我知道for循环是O(n)，但在调用indexOf函数时，查找当前字符会增加多少额外的时间？
public static String find(String input) {
String currentLongest = input.length() > 0 ? "" + input.charAt(0) : "";
String tmp = currentLongest;
for (int i = 1; i < input.length(); i++) {
int index = tmp.indexOf("" + input.charAt(i));
if (index == -1) {
tmp = tmp + input.charAt(i);
if (tmp.length() > currentLongest.length())
currentLongest = tmp;
} else
tmp = tmp.substring(index+1)+input.charAt(i);
}
return currentLongest;
}
英文:
I have the function below that finds the longest non repeating sub-string in a string.
I know the for loop is O(n) but what will be the additional time by searching current char in tmp string in call to function indexOf.
public static String find(String input) {
String currentLongest = input.length() > 0 ? "" + input.charAt(0) : "";
String tmp = currentLongest;
for (int i = 1; i < input.length(); i++) {
int index = tmp.indexOf(""+input.charAt(i));
if (index == -1) {
tmp = tmp + input.charAt(i);
if (tmp.length() > currentLongest.length())
currentLongest = tmp;
} else
tmp = tmp.substring(index+1)+input.charAt(i);
}
return currentLongest;
}
答案1
得分: 0
以下是已翻译的内容：
无论是indexOf()还是重新创建tmp（使用operator+），它们都在每次迭代中发生，都需要O(|S|)的时间，其中|S|是在这次迭代中tmp的长度。现在，问题是tmp的长度是否有界限？
如果您的字母表是有限的（例如，如果它只包含从a、b、...、z中的字符）- 那么tmp的长度是有限的（在a-z示例中为26，这来自于鸽巢原理）。在这种情况下，您可以说indexOf()和创建一个新字符串（使用operator+）都需要O(1)的时间，因为它创建了一个具有有界大小的字符串。在这种情况下，算法的时间复杂度为**O(n)**。
然而，如果字母表是无限的，您可以有一个输入字符串根本没有重复。在这种情况下，循环的每次迭代都需要O(i)的时间。这给了你。
1 + 2 + ... n = n (n+1)/2
这在O(n^2)内，算法的复杂性变为**O(n^2)**。
英文:
Both indexOf(), and recreating tmp (using operator+), which both happen in every iteration, takes O(|S|) time, where |S| is the length of tmp in this iteration. Now, the question is is the length of tmp bounded?
If your alphabet is limited (for example, if it can contain only characters from a,b,...,z) - then the length of tmp is of limited size (26 in the a-z example, this comes from pigeonhole principle). In this case, you can say that indexOf() and creating a new string (by using operator +) is taking O(1) time, since it is creating a string with bounded size. And in this case, the algorithm takes O(n) time.
However, if the alphabet is unlimited, you can have an input string with no repeatitions at all.
In this case, each iteration of the loop takes O(i) time. This gives you.
1 + 2 + ... n = n (n+1)/2
Which is in O(n^2), and the algorithm's complexity becomes O(n^2)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论