Notația Big-O: complexitatea temporală

Optimizarea codului în Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Ce este complexitatea temporală?

Complexitate temporală: măsoară cum crește timpul de execuție în funcție de dimensiunea intrării
Răspunde la: „Ce se întâmplă când datele cresc de 10×?"
Nu se focusează pe timpul absolut

Notația Big-O

Notație matematică pentru scenariul cel mai defavorabil.

Clase comune de complexitate:

O(1): Timp constant - independent de dimensiune

Înțelegerea lui O(1)

Un exemplu de operație O(1) este get() din ArrayList

Implementare internă (simplificată) a unui ArrayList cu String-uri:

public class ArrayList {}
    private String[] data; // Internal array
    private int size;

    // Get operation - direct array access
    public String get(int index) {
        return data[index]; // O(1)
    }
}

Notația Big-O

Notație matematică pentru scenariul cel mai defavorabil

Clase comune de complexitate:

O(1): Timp constant - independent de dimensiune
O(n): Timp liniar - crește cu dimensiunea intrării

Înțelegerea lui O(n)

Un exemplu similar, pentru contains() din ArrayList

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    // Linear search through array
    for (int i = 0; i < size; i++) {
        if (o.equals(elementData[i])) {
            return i;
        }
    }
    return -1; // Not found
}

Notația Big-O

Notație matematică pentru scenariul cel mai defavorabil

Clase comune de complexitate:

O(1): Timp constant - independent de dimensiune
O(n): Timp liniar - crește cu dimensiunea intrării
O(n²): Timp pătratic - crește pătratic cu dimensiunea intrării

Exemplu practic de complexitate pătratică

// Finding a pair of numbers that sum to a target value
// Time complexity: O(n²)

public int[] findPairWithSum(ArrayList<Integer> numbers, int targetSum) {
    for (int i = 0; i < numbers.size(); i++) {
        for (int j = i + 1; j < numbers.size(); j++) {
            if (numbers.get(i) + numbers.get(j) == targetSum) {
                console.log("Found them!")
            }
        }
    }
}

De ce contează complexitatea temporală

Impactul dimensiunii intrării:

O(1): 1.000 -> 1.000.000 elemente = Același timp!
O(n): 1.000 -> 1.000.000 elemente = De 1.000× mai lent
O(n²): 1.000 -> 1.000.000 elemente = De 1.000.000× mai lent

Grafic comparativ al claselor de complexitate

Să exersăm!

Optimizarea codului în Java