Big-O notace: časová složitost

Optimalizace kódu v Javě

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Co je časová složitost?

Časová složitost: míra toho, jak roste doba běhu s velikostí vstupu
Pomáhá odpovědět: "Co se stane, když se data zvětší 10×?"
Nezaměřuje se na absolutní čas

Big-O notace

Matematická notace pro popis nejhoršího případu.

Některé běžné třídy složitosti:

O(1): Konstantní čas – nezávislý na velikosti vstupu

Porozumění O(1)

Příkladem operace O(1) je metoda get() třídy ArrayList

Zjednodušená interní implementace třídy ArrayList pro typ String:

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

Big-O notace

Matematická notace pro popis nejhoršího případu

Některé běžné třídy složitosti:

O(1): Konstantní čas – nezávislý na velikosti vstupu
O(n): Lineární čas – roste s velikostí vstupu

Porozumění O(n)

Podobný příklad, tentokrát pro metodu contains() třídy 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
}

Big-O notace

Matematická notace pro popis nejhoršího případu

Některé běžné třídy složitosti:

O(1): Konstantní čas – nezávislý na velikosti vstupu
O(n): Lineární čas – roste s velikostí vstupu
O(n²): Kvadratická čas – roste kvadraticky s velikostí vstupu

Praktický příklad s kvadratickou složitostí

// 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!")
            }
        }
    }
}

Proč záleží na časové složitosti

Vliv velikosti vstupu:

O(1): 1 000 -> 1 000 000 prvků = Stejný čas!
O(n): 1 000 -> 1 000 000 prvků = 1 000× pomalejší
O(n²): 1 000 -> 1 000 000 prvků = 1 000 000× pomalejší

Graf časové složitosti

Lass uns üben!

Optimalizace kódu v Javě