英文:
What is the time complexity of String compareTo function in Java?
问题
我有一个字符串数组 String strs[] = {"flower", "flow", "flight"};。
我想从数组中找到字典序最小和最大的字符串。
这是我所做的：
String first = strs[0], last = strs[0];
for (String str : strs) {
if (str.compareTo(first) < 0)
first = str;
if (str.compareTo(last) > 0)
last = str;
}
System.out.println("First: " + first + " Last: " + last);
现在我想要找出这个算法的时间复杂度。我知道它将是 n * (compareTo() 的时间复杂度)。那么，这个算法的时间复杂度是多少？
英文:
I have a String array String strs[] = {"flower", "flow", "flight"};.
I want to find the smallest and largest lexicographically string from the array.
This is what I did:
String first = strs[0], last = strs[0];
for (String str : strs) {
if (str.compareTo(first) < 0)
first = str;
if (str.compareTo(last) > 0)
last = str;
}
System.out.println("First : " + first + " Last : " + last);
Now I want find the time complexity of this algorithm. I know it will be n * (time complexity of compareTo()). So, what is the time complexity of this algorithm?
答案1
得分: 3
这是String#compareTo方法的实现，考虑到最坏情况下（len1 = len2 = n），复杂度为O(n)。
因此，您的算法复杂度将为O(nm)，其中n为数组中的字符串数，m为这些字符串长度中的最大长度。
英文:
public int compareTo(String anotherString) {
int len1 = value.length;
int len2 = anotherString.value.length;
int lim = Math.min(len1, len2);
char v1[] = value;
char v2[] = anotherString.value;
int k = 0;
while (k < lim) {
char c1 = v1[k];
char c2 = v2[k];
if (c1 != c2) {
return c1 - c2;
}
k++;
}
return len1 - len2;
}
This is the implementation of String#compareTo which leads to consider the complexity, in the worst case scenario (len1 = len2 = n), as O(n)
So the complexity of your algorithm would be O(nm) with n = number of strings in your array and m the max length among those strings lenghts.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论