Открывается в новой вкладке

Мы всегда на связи

Пишите в любое удобное время:
whatsappvktelegramMAX
Или задайте вопрос через форму:

Мы всегда на связи

Заявка принята!

Мы уже получили заявку и скоро свяжемся. Расскажите немного о ребёнке — так быстрее подберём группу (необязательно).

Спасибо!

Мы свяжемся с вами в ближайшее время.

Учебник по информатике и математике

Структурированные пути обучения: от первых программ до олимпиад и вступительных в топ-школы.
    Темы
    Заниматься с наставником
    прочитали
    3 задачи

    Сложность алгоритма и O-нотация

    Оглавление:

    Ты отправляешь решение олимпиадной задачи на проверку. Первые тесты проходят мгновенно, а на последнем система пишет: «Превышено ограничение времени». Программа не сломалась — просто на тесте с миллионом чисел ей нужна не секунда, а почти три часа.

    Понять это заранее, не запуская программу, помогает сложность алгоритма — оценка того, как растет объем работы, когда данных становится больше.

    Считаем операции, а не секунды

    Время в секундах зависит от многого: от мощности компьютера, языка программирования, других запущенных программ. Поэтому скорость алгоритма меряют не секундомером, а числом элементарных операций: сравнений, присваиваний, сложений, обращений к элементу массива.

    Число операций зависит от размера входных данных — его обозначают буквой $n$. Для массива $n$ — это количество элементов. Чтобы сложить все элементы, нужно $n$ сложений, а чтобы сравнить каждый элемент с каждым — около $n^2$ сравнений.

    Обычно оценивают худший случай. Линейный поиск может найти число с первой попытки, но гарантировать можно одно: он сделает не больше $n$ сравнений.

    Что значит $O(...)$

    Допустим, алгоритм делает $3n^2 + 5n + 7$ операций. При $n = 1000$ первое слагаемое дает 3 000 000, а два остальных вместе — всего 5007. Главное слагаемое решает все, поэтому младшие отбрасывают, а заодно и множитель 3: он зависит от того, что считать одной операцией. Остается $n^2$, и пишут: сложность алгоритма $O(n^2)$, читается «о большое от эн квадрат».

    Ключевая идея: $O(...)$ показывает не точное число операций, а скорость роста. Если сложность $O(n^2)$, то при росте $n$ в 10 раз работы станет примерно в 100 раз больше.

    Главные классы сложности:

    • $O(1)$ — время не зависит от $n$: взять элемент a[i], узнать длину списка len(a);
    • $O(\log n)$ — задача на каждом шаге уменьшается вдвое, как в бинарном поиске;
    • $O(n)$ — один проход по массиву: сумма, поиск максимума, линейный поиск;
    • $O(n \log n)$ — быстрые сортировки, в том числе встроенные sorted() в Python и sort() в C++;
    • $O(n^2)$ — два вложенных цикла: сравнить все пары, сортировка пузырьком или выбором.

    Как растет число операций

    Логарифм здесь по основанию 2, числа округлены:

    Сложность $n = 10$ $n = 1000$ $n = 1\,000\,000$
    $O(1)$ 1 1 1
    $O(\log n)$ 3 10 20
    $O(n)$ 10 1000 1 000 000
    $O(n \log n)$ 33 10 000 20 000 000
    $O(n^2)$ 100 1 000 000 1 000 000 000 000

    Компьютер выполняет порядка $10^8$ простых операций в секунду (это для C++, Python в десятки раз медленнее). При миллионе элементов алгоритм за $O(n \log n)$ справится за доли секунды, а за $O(n^2)$ будет работать около $10^4$ секунд — почти три часа. Вот что случилось с решением из начала статьи.

    Отсюда правило для олимпиад: при $n$ до нескольких тысяч пройдет и $O(n^2)$, а при $n$ около $10^6$ нужен $O(n)$ или $O(n \log n)$.

    Как оценить сложность по коду

    1. Действия без циклов стоят $O(1)$.
    2. Цикл из $n$ шагов умножает стоимость тела на $n$. Вложенные циклы перемножаются: $n \cdot n = n^2$.
    3. Части, которые идут друг за другом, складываются, и остается самая тяжелая: $O(n) + O(n^2) = O(n^2)$.
    4. Если переменная цикла каждый раз делится пополам, шагов будет около $\log_2 n$.

    Проверим правила: посчитаем шаги трех циклов при разных $n$.

    def halving(n):      # O(log n): делим n пополам
        steps = 0
        while n > 1:
            n //= 2
            steps += 1
        return steps
    
    
    def linear(n):       # O(n): один проход
        steps = 0
        for i in range(n):
            steps += 1
        return steps
    
    
    def pairs(n):        # O(n^2): все пары (i, j)
        steps = 0
        for i in range(n):
            for j in range(n):
                steps += 1
        return steps
    
    
    for n in [10, 1000]:
        print(n, halving(n), linear(n), pairs(n))
    # 10 3 10 100
    # 1000 9 1000 1000000
    

    То же на C++:

    #include <iostream>
    using namespace std;
    
    long long halving(long long n) {   // O(log n)
        long long steps = 0;
        while (n > 1) {
            n /= 2;
            steps++;
        }
        return steps;
    }
    
    long long linear(long long n) {    // O(n)
        long long steps = 0;
        for (long long i = 0; i < n; i++) steps++;
        return steps;
    }
    
    long long pairs(long long n) {     // O(n^2)
        long long steps = 0;
        for (long long i = 0; i < n; i++)
            for (long long j = 0; j < n; j++) steps++;
        return steps;
    }
    
    int main() {
        long long sizes[] = {10, 1000};
        for (long long n : sizes)
            cout << n << " " << halving(n) << " " << linear(n) << " " << pairs(n) << "\n";
        // 10 3 10 100
        // 1000 9 1000 1000000
    }
    

    Пример посложнее: есть ли в массиве одинаковые числа? Сравним a[i] с каждым элементом правее. Если повторов нет, сравнений будет $(n - 1) + (n - 2) + \ldots + 1 = \frac{n(n - 1)}{2} = \frac{n^2}{2} - \frac{n}{2}$. Отбрасываем множитель и младшее слагаемое: $O(n^2)$. Быстрее — сначала отсортировать массив за $O(n \log n)$: одинаковые числа окажутся рядом, и хватит одного прохода по соседям. Итого $O(n \log n) + O(n) = O(n \log n)$.

    Частая ошибка: Пропустить скрытый цикл. Проверка x in a для списка, a.index(x), a.count(x), срез a[1:] сами проходят по списку и стоят $O(n)$. Внутри цикла по тому же списку они дают $O(n^2)$, хотя вложенного цикла в коде не видно. И наоборот: два цикла друг за другом — это $O(n) + O(n) = O(n)$, а не $O(n^2)$.

    Проверь себя

    1.

    В программе сначала идет цикл for i in range(n), а после него — еще один такой же цикл for j in range(n). В каждом цикле одна операция. Какая сложность у программы?

    2.

    Алгоритм работает за $O(n^2)$. Во сколько раз примерно вырастет число операций, если $n$ увеличить в 10 раз?

    3.

    Соедини сложность и пример алгоритма.

    $O(1)$

    Встроенная сортировка sorted()

    $O(\log n)$

    Найти максимум в массиве

    $O(n)$

    Сравнить каждый элемент с каждым

    $O(n \log n)$

    Взять элемент массива по индексу

    $O(n^2)$

    Бинарный поиск в отсортированном массиве

    Поможем подобрать обучение

    Оставьте телефон. Мы перезвоним, поможем выбрать подходящие занятия и ответим на вопросы

    Поможем подобрать обучение

    Заявка принята.

    Мы свяжемся с вами