Độ phức tạp về thời gian của hàm String CompareTo trong Java là gì?

Question

Tôi có một mảng Chuỗi String strs[] = {"flower", "flow", "flight"};.

Tôi muốn tìm chuỗi từ điển nhỏ nhất và lớn nhất từ ​​mảng. Đây là những gì tôi đã làm:

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);

Bây giờ tôi muốn tìm độ phức tạp về thời gian của thuật toán này. Tôi biết nó sẽ là n * (thời gian phức tạp của compareTo()). Vì vậy, độ phức tạp thời gian của thuật toán này là gì?

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;
}

Đây là việc triển khai String # so sánhTo dẫn đến việc xem xét độ phức tạp, trong trường hợp xấu nhất (len1 = len2 = n), là O (n)

Vì vậy, độ phức tạp của thuật toán của bạn sẽ là O (nm) với n = số chuỗi trong mảng của bạn và m độ dài tối đa trong số các chuỗi đó.