Java中String compareTo函数的时间复杂度是多少？

Question

我有一个字符串数组 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() 的时间复杂度）。那么，这个算法的时间复杂度是多少？

Answer 1

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中String compareTo函数的时间复杂度是多少？

What is the time complexity of String compareTo function in Java?

java

string

algorithm

time-complexity