O-нотация light version
Содержание
O-нотация для самых маленьких
В этой статье объяснено, как оценивать время работы алгоритмов в простейших случаях, без точных определений и теоретических изысков.
Зачем это нужно
Казалось бы, что для оценки времени работы можно просто физически измерять время, которое программа работает на разных входных данных. Здесь есть достаточное количество минусов:
- на разных компьютерах время работы будет разным;
- чтобы измерить время, придется запустить сам алгоритм, но иногда приходится оценивать алгоритмы, требующие часы или даже дни работы;
- время будет учитывать какие-то вспомогательные операции, которые на самом деле в текущей оценке не нужны
Зачастую основной задачей программиста становится оптимизировать алгоритм, выполнение которого займёт тысячи лет, до какого-нибудь адекватного времени работы. Поэтому хотелось бы уметь предсказывать, сколько времени займёт выполнение алгоритма ещё до того, как мы его запустим.
Что и как учитывать
Чаще всего мы будем считать, что за условную единицу времени выполняются следующие операции (тут приведены не все, но принцип здесь виден):
- арифметические операции ($*$, $+$, $-$, $/$, битовые сдвиги);
- сравнение чисел;
- присваивание;
Мы можем попробовать точно оценить количество таких операций, которые выполняются в программе. Но в большинстве случаев такого подробного разбора всех действий не требуется. Если вы посчитаете, сколько операций сравнения происходит в разных квадратичных сортировках, то получите разные выражения, где главный член - это $N^2$, умноженное на некоторую константу. Хочется придумать способ упростить эти формулы так, чтобы:
- не нужно было учитывать много информации, не очень сильно влияющей на итоговое время;
- легко было оценивать время работы разных алгоритмов для больших чисел;
- легко было сравнивать алгоритмы на предмет того, какой из них лучше подходит для тех или иных входных данных.
O-нотация
Для этого придумали $O$-нотацию - асимптотическое время работы вместо точного (часто его ещё называют асимптотикой).
Пусть $f(N)$ - это какая-то функция. Говорят, что алгоритм работает за $O(f(N))$, если существует число $C$, такое что алгоритм работает не более чем за $C \cdot f(N)$ операций.
В таких обозначениях можно сказать, что
- Сортировка пузырьком работает за $O(N^2)$
- Сортировка выбором работает за $O(N^2)$
- Сортировка вставками работает за $O(N^2)$
- Сортировка подсчетом работает за $O(N + M)$
Это обозначение удобно тем, что оно короткое и понятное, а также оно не зависит от умножения на константу или прибавления константы. Если алгоритм работает за $O(N^2)$, то это может значить, что он работает за $N^2$, за $N^2 + 3$, за $\frac{N(N-1)}{2}$ или даже за $1000 \cdot N^2 + 1$ действие. Главное, что функция ведет себя как $N^2$, то есть при увеличении $N$ (в данном случае это длина массива) он увеличивается как некоторая квадратичная функция. Например, если увеличить $N$ в $10$ раз, время работы программы увеличится приблизительно в $100$ раз.
Поэтому все эти рассуждения про то, сколько операций в `swap` или считать ли отдельно присваивания, сравнения и циклы - отпадают. Как бы вы ни ответили на эти вопросы, они меняют ответ на константу, а значит асимптотическое время работы алгоритма никак не меняется.
Задания
- Найдите асимптотику данных функций. Максимально упростите ответ (например, до $O(N)$, $O(N^2)$ и т. д.).
- $\frac{N}{3}$
- $\frac{N(N-1)(N-2)}{6}$
- $1 + 2 + 3 + \ldots + N$
- $1^2 + 2^2 + 3^2 + \ldots + N^2$
- $\log{N} + 3$
- $7$
- $10^{100}$
- Найдите асимптотическое время работы данных функций:
int f(int n) { int s = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { s += i * j; } } return s; }
int g(int n) { int s = 0; for (int i = 0; i < n; i++) { s += i; } for (int i = 0; i < n; i++) { s += i * i; } return s; }
int h(int n) { if (n == 0) { return 1; } return h(n - 1) * n; }
- Найдите асимптотики, за которые работают эффективные алгоритмы, решающие данные задачи:
- написать числа от $1$ до $N$;
- написать все тройки чисел от $1$ до $N$;
- найти разницу между максимумом и минимумом в массиве;
- найти число единиц в бинарной записи числа $N$.
Автор конспекта: Полина Романченко
По всем вопросам пишите в telegram @Romanchenko