我有一个字符串数组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() 的时间复杂度)。那么,这个算法的时间复杂度是多少?
最佳答案
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;
}
这是 String#compareTo 的实现,它导致考虑复杂性,在最坏的情况下 (len1 = len2 = n),为 O(n)
因此,算法的复杂度为 O(nm),其中 n = 数组中的字符串数量,m 为这些字符串长度中的最大长度。
关于java - Java中String CompareTo函数的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64558454/