Qual è la complessità temporale della funzione String compareTo in Java?

Question

Ho un array di stringhe String strs[] = {"flower", "flow", "flight"};.

Voglio trovare la stringa lessicograficamente più piccola e più grande dall'array. Questo è quello che ho fatto:

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

Ora voglio trovare la complessità temporale di questo algoritmo. So che sarà n * (complessità temporale di compareTo()). Allora, qual è la complessità temporale di questo 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;
}

Questa è l'implementazione di String # compareTo che porta a considerare la complessità, nel caso peggiore (len1 = len2 = n), come O (n)

Quindi la complessità del tuo algoritmo sarebbe O (nm) con n = numero di stringhe nel tuo array e m la lunghezza massima tra quelle lunghezze di stringhe.