Нотація Big-O: часова складність

Оптимізація коду в Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Що таке часова складність?

Часова складність: як зростає час виконання зі збільшенням вхідних даних
Допомагає відповісти: «Що буде, коли даних стане у 10× більше?»
Не про абсолютний час

Нотація Big-O

Математична нотація для опису найгіршого випадку.

Поширені класи складності:

O(1): Константний час — не залежить від розміру

Розуміння O(1)

Приклад операції O(1): get() у ArrayList

Внутрішня (спрощена) реалізація ArrayList, що зберігає Strings:

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

Математична нотація для опису найгіршого випадку

Поширені класи складності:

O(1): Константний час — не залежить від розміру
O(n): Лінійний час — зростає з розміром вхідних даних

Розуміння O(n)

Подібний приклад для contains() у 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

Математична нотація для опису найгіршого випадку

Поширені класи складності:

O(1): Константний час — не залежить від розміру
O(n): Лінійний час — зростає з розміром вхідних даних
O(n²): Квадратичний час — зростає квадратично з розміром вхідних даних

Практичний приклад із квадратичною складністю

// Пошук пари чисел, що в сумі дають цільове значення
// Часова складність: 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!")
            }
        }
    }
}

Чому часова складність важлива

Вплив розміру вхідних даних:

O(1): 1 000 -> 1 000 000 елементів = той самий час!
O(n): 1 000 -> 1 000 000 елементів = у 1 000× повільніше
O(n²): 1 000 -> 1 000 000 елементів = у 1 000 000× повільніше

Screenshot 2025-05-10 at 2.27.06 PM.png

Давайте потренуємось!

Оптимізація коду в Java