Notacja Big-O: złożoność czasowa

Optymalizacja kodu w Javie

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Czym jest złożoność czasowa?

Złożoność czasowa: miara wzrostu czasu działania wraz z rozmiarem danych
Odpowiada na pytanie: „Co się stanie, gdy danych będzie 10× więcej?"
Nie odnosi się do czasu bezwzględnego

Notacja Big-O

Notacja matematyczna opisująca scenariusz najgorszego przypadku.

Najpopularniejsze klasy złożoności:

O(1): Czas stały – niezależny od rozmiaru

Zrozumieć O(1)

Przykładem operacji O(1) jest metoda get() klasy ArrayList

Uproszczona implementacja klasy ArrayList przechowującej obiekty 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)
    }
}

Notacja Big-O

Notacja matematyczna opisująca scenariusz najgorszego przypadku

Najpopularniejsze klasy złożoności:

O(1): Czas stały – niezależny od rozmiaru
O(n): Czas liniowy – rośnie wraz z rozmiarem danych

Zrozumieć O(n)

Podobny przykład, ale dla metody contains() klasy 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
}

Notacja Big-O

Notacja matematyczna opisująca scenariusz najgorszego przypadku

Najpopularniejsze klasy złożoności:

O(1): Czas stały – niezależny od rozmiaru
O(n): Czas liniowy – rośnie wraz z rozmiarem danych
O(n²): Czas kwadratowy – rośnie kwadratowo wraz z rozmiarem danych

Praktyczny przykład złożoności kwadratowej

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

Dlaczego złożoność czasowa ma znaczenie

Wpływ rozmiaru danych wejściowych:

O(1): 1 000 -> 1 000 000 elementów = Ten sam czas!
O(n): 1 000 -> 1 000 000 elementów = 1 000× wolniej
O(n²): 1 000 -> 1 000 000 elementów = 1 000 000× wolniej

Wykres złożoności czasowej

Czas na ćwiczenia!

Optymalizacja kodu w Javie