Временная сложность

Когда мы с вами программируем очередной алгоритм, мы хотим понять за сколько времени он будет выполнен. Для этого, казалось бы, мы можем использовать 2 разных компьютера - мой и ваш. Но из-за разницы в скорости работы процессора, мы не сможем полагаться на полученный результат.

В этом случае на помощь нам приходит абстрактная модель, называемая Big O нотация. Она позволяет оценить сложность каждого отдельно взятого алгоритма. Звучит она так - от передаваемых параметров зависит количество операций, которые будут выполнены перед тем, как алгоритм завершится. Обратите внимание на слова "параметры" и "операции".

Скорость алгоритма -> это влияние темпов роста параметров, на количество операций. Скорость работы алгоритма не измеряется в секундах.

Big O, Big Omega (Ω), Big Theta (Θ)

Big O (O) - верхняя граница работы алгоритма - худший сценарий

Big Omega (Ω) - нижняя граница работы алгоритма - лучший сценарий

Big Theta (Θ) - когда верхняя граница равна нижней границе - то есть, Big O (O) и Big Omega (Ω) одновременно