Big O notation

Big O - обозначение за сколько действий выполняется алгоритм Считается, что C++ может выполнять $2\ast 10^8$ операций в секунду Python - около $10^7$ операций

Скорость алгоритма определяется самой медленной частью алгоритма Сложность рекурсивного алгоритма определяется тем, сколько раз вызывается рекурсивная функция

n - входные данные

---

$O(1)$ - Алгоритм с постоянной сложностью. Скорость не зависит от входных данных $O(n^K)$ - Алгоритм с $k$ вложенным циклов $O(\log n)$ - Алгоритм, на каждом шаге которого уменьшается количество входящих данных $O(n)$ - Линейный алгоритм. Скорость выполнения прямо пропорциональна от количества входных данных $O(n\log n)$ - Алгоритм сортирует данные, либо использует структуру данных, работающую со скоростью $O(\log n)$ $O(2^n)$ - Алгоритм перебирает все подмножества каждого входного данного $O(n!)$ - Алгоритм перебирает все перестановки входных данных