Сложность алгоритмов и O-нотация
Как оценить скорость алгоритма до запуска: O-нотация и правило 10⁸ операций в секунду.
Правильный ответ — только половина олимпиадной задачи. Вторая половина — уложиться в лимит времени, обычно 1–2 секунды. Поэтому первое, чему учится олимпиадник, — оценивать скорость алгоритма ДО того, как писать код.
Скорость измеряют количеством операций в зависимости от размера входа n и записывают через O-нотацию (читается «о большое»):
• O(1) — константа: ответ по формуле;
• O(log n) — деление задачи пополам: бинарный поиск;
• O(n) — один проход по данным;
• O(n log n) — сортировка;
• O(n²) — два вложенных цикла;
• O(2ⁿ) — полный перебор подмножеств.
Главное практическое правило: компьютер выполняет порядка 10⁸ простых операций в секунду. Подставьте свой n в формулу сложности — и вы знаете, пройдёт решение или нет.
Сколько операций потребует каждый алгоритм? Введите n, например: 100000
Попробуйте ввести 1000, потом 100000, потом 1000000000 — и сравните строки с правилом 10⁸. Видно, почему решение за O(n²) при n = 10⁵ уже не проходит (10¹⁰ операций — сто секунд), а за O(n log n) — легко.
Почувствуйте разницу вживую: программа ниже считает сумму чисел от 1 до n двумя способами — циклом за O(n) и формулой за O(1). Введите 1000000000 (миллиард) и посмотрите на время выполнения: цикл займёт заметное время, формула — мгновение. Ответы совпадут.
Введите 1000000000 и сравните: цикл заметно думает, формула мгновенна
Как оценивать свой код:
• вложенные циклы перемножаются: цикл по n внутри цикла по n — это O(n²);
• последовательные блоки складываются, и берётся наибольший: O(n) + O(n log n) = O(n log n);
• константы отбрасываются: 5n операций — это всё равно O(n).
Задание: оцените сложность трёх фрагментов — (1) поиск максимума одним проходом; (2) проверка всех пар элементов; (3) цикл, в котором n каждый раз делится на 2. Ответы: O(n), O(n²), O(log n).
Решите прикреплённую задачу «Сумма элементов массива» — классический один проход за O(n) — и отметьте урок пройденным.