¿Cuál es la complejidad temporal de la función String compareTo en Java?

Question

Tengo una matriz de cadenas String strs[] = {"flower", "flow", "flight"};.

Quiero encontrar la cadena lexicográficamente más pequeña y más grande de la matriz. Esto es lo que hice:

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

Ahora quiero encontrar la complejidad temporal de este algoritmo. Sé que será n * (complejidad de tiempo de compareTo()). Entonces, ¿cuál es la complejidad temporal de este algoritmo?

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

Esta es la implementación de String # compareTo que lleva a considerar la complejidad, en el peor de los casos (len1 = len2 = n), como O (n)

Entonces, la complejidad de su algoritmo sería O (nm) con n = número de cadenas en su matriz y m la longitud máxima entre esas longitudes de cadenas.