Правила упрощения обозначений Big O

Нотация Big O – это язык, на котором мы говорим о том, сколько времени занимает выполнение алгоритма. Он позволяет рассчитать, насколько эффективным является способ решения проблемы.

Ознакомьтесь с основами нотации Big O Notation здесь – Learn to Code – Big O Notation

Чтобы упростить выражения в нотации Big O, мы следуем ряду правил.

  1. Арифметические операции постоянны. Например, вашему компьютеру требуется почти одинаковое время для вычисления 2+2 и 20,465+2.

  2. Назначения переменных также постоянны. Как и в случае с арифметическими операциями, компьютеру требуется одинаковое количество времени, чтобы присвоить значение переменной, будь то x = 3 или x = 509.

  3. Доступ к элементам массива по индексу или к объекту по ключу является постоянным.

  4. В цикле сложность равна длине цикла, умноженной на сложность всего, что происходит внутри цикла. Например, если у нас есть вложенные циклы, мы будем иметь 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).

Оцените статью
Procodings.ru
Добавить комментарий