Нотация Big-O: временна́я сложность

Оптимизация кода на Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Что такое временна́я сложность?

Временна́я сложность: мера роста времени выполнения при увеличении входных данных
Помогает ответить на вопрос: «Что произойдёт, если данных станет в 10 раз больше?»
Не зависит от абсолютного времени выполнения

Нотация Big-O

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

Распространённые классы сложности:

O(1): константное время — не зависит от размера

Понимание O(1)

Пример операции O(1) — метод get() у ArrayList

Упрощённая реализация ArrayList для хранения 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

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

Распространённые классы сложности:

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²): квадратичное время — растёт квадратично от размера входных данных

Практический пример с квадратичной сложностью

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

Почему важна временна́я сложность

Влияние размера входных данных:

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 раз медленнее

Скриншот 2025-05-10 в 14:27:06

Давайте потренируемся!

Оптимизация кода на Java