Нотация Big O — это язык, на котором мы говорим о том, сколько времени занимает выполнение алгоритма. Он позволяет рассчитать, насколько эффективным является способ решения проблемы.
Ознакомьтесь с основами нотации Big O Notation здесь — Learn to Code — Big O Notation
Чтобы упростить выражения в нотации Big O, мы следуем ряду правил.
-
Арифметические операции постоянны. Например, вашему компьютеру требуется почти одинаковое время для вычисления 2+2 и 20,465+2.
-
Назначения переменных также постоянны. Как и в случае с арифметическими операциями, компьютеру требуется одинаковое количество времени, чтобы присвоить значение переменной, будь то x = 3 или x = 509.
-
Доступ к элементам массива по индексу или к объекту по ключу является постоянным.
-
В цикле сложность равна длине цикла, умноженной на сложность всего, что происходит внутри цикла. Например, если у нас есть вложенные циклы, мы будем иметь
n^2времени выполнения.
Давайте рассмотрим пример кода —
function logAtLeast5(n){
for(var i=1, i<=math.max(5,n), (i++)
console.log(i);
}
}
Здесь у нас есть цикл, и этот цикл будет идти от единицы до пяти или до конца, в зависимости от того, что больше.
Что происходит, когда ‘n’ становится больше и продолжает расти и расти и расти к бесконечности? Большое O этого —O(n), потому что по мере роста ‘n’ количество операций растет пропорционально ‘n’. На графике мы можем увидеть общую траекторию для O(n).