Big O нотация нужна для описания сложности алгоритмов. Для этого используется понятие времени.
Big-O позволяет оценить, насколько время выполнения алгоритма зависит от переданных в него данных.
Начнем с самого простого: O(1)
Возьмем массив из 5 чисел:
const nums = [1,2,3,4,5];Допустим надо получить первый элемент. Используем для это индекс:
const nums = [1,2,3,4,5];
const firstNumber = nums[0];Насколько это сложный алгоритм? Можно сказать: «совсем не сложный — просто берем первый элемент массива». Это верно, но корректнее описывать сложность через количество операций, выполняемых для достижения результата, в зависимости от ввода (операций на ввод).
Другими словами: насколько возрастет кол-во операций при увеличении кол-ва входных параметров.
В нашем примере входных параметров 5, потому что в массиве 5 элементов. Для получения результата нужно выполнить одну операцию (взять элемент по индексу). Сколько операций потребуется если элементов массива будет 100? Или 1000? Или 100 000? Все равно нужна только одна операция.
Т.е.: «одна операция для всех возможных входных данных» — O(1).
O(1) можно прочитать как «сложность порядка 1» (order 1), или «алгоритм выполняется за постоянное/константное время» (constant time).
Вы уже догадались что O(1) алгоритмы самые эффективные.
Итерации и «время порядка n»: O(n)
Теперь давайте найдем сумму элементов массива:
const nums = [1,2,3,4,5];
let sum = 0;
for(let num of nums){
sum += num;
}Опять зададимся вопросом: сколько операций на ввод нам потребуется? Здесь нужно перебрать все элементы, т.е. операция на каждый элемент. Чем больше массив, тем больше операций.
Используя Big O нотацию: O(n), или «сложность порядка n (order n)». Так же такой тип алгоритмов называют «линейными» или что алгоритм «линейно масштабируется».
