Что такое нотация большого O?

Обозначение «большое О» — это символ того, насколько быстро растет (математическая) функция. В информатике нотация Big O используется для представления эффективности вашего алгоритма/программного обеспечения. Это важно, потому что это повлияет на производительность того, что вы строите.

Обозначение Big O измеряет, насколько увеличится время выполнения при увеличении ввода. Звучит запутанно? Это делает для меня. Вот несколько примеров, которые помогли мне понять это.

«Постоянное время»

Следующий код печатает первый элемент массива:

const fruitArray = ["apples", "orranges", "grapes"]  
function printFirstFruit(array) {          
    console.log(array[0]) 
}  
printFirstFruit(fruitArray);

При запуске эта функция должна выполнить один «шаг», и это не изменится независимо от того, что вы вводите — независимо от того, насколько велик массив. Обозначение Big O, используемое для представления этого, равно O (1), поскольку эта функция выполняется в «постоянное время».

«Линейное время»

Эта функция печатает каждый элемент массива:

const fruitArray = ["apples", "oranges", "grapes"]  
function printEachFruit(array) {          
    array.forEach(item => {         
        console.log(item)     
    } 
}  
printEachFruit(fruitArray);

В этом случае функция должна выполнить один «шаг» для каждого элемента массива. Это означает, что если у вас есть 3 элемента в массиве, функция выполняет 3 шага; если у вас есть 300 элементов в массиве, функция выполняет 300 шагов, а если у вас есть 3000 элементов в массиве, функция выполняет 3000 шагов и т. д.

Этот тип функции работает в «линейном времени», что означает, что время выполнения увеличивается линейно с вашим вводом. Он выполняется за время O(n), где n — количество элементов в массиве.

«Квадратичное время»

Что, если ваш код выглядит так?

const homeArray = ["book", "chair", "table", "sofa"] 
homeArray.forEach(firstItem => { 	
    homeArray.forEach(secondItem => { 
        console.log(firstItem + secondItem) 	
    }) 
})

Ваш вывод будет выглядеть так:

bookbook bookchair booktable booksofa 
chairbook chairchair chairtable chairsofa 
tablebook tablechair tabletable tablesofa 
sofabook sofachair sofatable sofasofa

На функцию, имеющую такие вложенные циклы, можно ссылаться с помощью нотации Big O O(n²),где n — количество элементов в массиве. Время выполнения такой функции будет увеличиваться квадратично по отношению к вашему вводу. Это связано с тем, что внешний цикл проходит через каждый элемент в массиве (т. е. он выполняется n раз), а для каждой итерации внешнего цикла внутренний цикл проходит через каждый элемент в массиве (т. е. он выполняет n x n, что равно n²).

Короче говоря, внешний цикл повторяется nраз, а внутренний цикл повторяется nраз для каждой итерации внешнего цикла. Это дает нам в общей сложности nx n “шагов”, что составляет n². Это называется «квадратичное время».

Алгоритмы поиска

Если у вас есть массив, который выглядит примерно так:

let numberArray = [1, 2, 3, 4, 6, 7, 10, 11, 12, 15, 18]

Как бы вы искали число 10? Мы рассмотрим два алгоритма поиска — линейный поиск и бинарный поиск.

Линейный поиск

Если вы используете алгоритм линейного поиска, вы будете последовательно перемещаться по массиву, пока не найдете совпадение или не дойдете до конца массива. Что такое нотация Big O для линейного поиска? Вам нужно выполнить один «шаг» (сравнение с числом, которое вы ищете) для каждого элемента в массиве; следовательно, это O(n), где n — количество элементов в массиве.

Бинарный поиск

Бинарный поиск работает иначе, чем линейный поиск — он похож на то, как люди ищут слова в словаре. Если вы используете бинарный поиск, вы перейдете к середине отсортированного массива и проверите, меньше или больше искомое число, чем число в середине массива. Это говорит вам, в какой половине находится нужное число. Затем вы будете повторять это для половины, в которой находится желаемое число, пока не найдете число.

Чтобы ясно понять это, давайте возьмем приведенный выше массив и найдем число 10. Наш первый шаг — перейти к середине массива — numberArray[5], который равен 7. 10 больше или меньше 7? Он больше, поэтому теперь мы выполняем тот же шаг на большей половине.

Мы идем к середине этой половины — numberArray[8], который равен 12. 10 больше или меньше 12? Оно меньше, поэтому теперь мы выполняем тот же шаг с меньшей половиной и продолжаем этот процесс, пока не найдем нужное число.

В этом примере мы найдем желаемое число относительно быстро, но чтобы понять возможности бинарного поиска, представьте, что мы пытаемся выполнить поиск в гораздо большем массиве. Бинарный поиск выполняется за время O(log n).

Обнаружили ли вы проблему с бинарным поиском? Двоичный поиск работает, только если ваш массив отсортирован. Если он не отсортирован, вам нужно будет отсортировать массив (для чего нужна отдельная запись в блоге), а затем использовать двоичный поиск.

Вывод

Нотация Big O — одна из краеугольных основ программирования. Хотя сначала это немного сложно понять, это действительно важно, если вы хотите, чтобы ваше программное обеспечение было максимально эффективным.