На Big O Notation есть, казалось бы, гигантская гора информации. Давайте разберемся, что это такое и что нам нужно знать, чтобы эффективно ориентироваться в нем.

Что это?

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

Как он рассчитывается?

Нотация Big O делится на несколько групп по скорости.

Постоянное время O(1)

Выполнение этих функций занимает одинаковое количество времени независимо от того, насколько большим становится n. Подумайте о поиске массива с индексом 0.

function lookUpThisThing(arrayOfThings) {
     console.log(arrayOfThings[1])
}

Линейное время O(n)

Linear Time описывает функции, которые напрямую связаны с размером n. Подумайте об итерации массива из 5 элементов по сравнению с массивом из 10 000 элементов.

function printThisArray(array) {
     array.forEach(arrayThing => {
          console.log(arrayThing)
     })
}

Квадратичное время O (n²)

Эти функции по существу представляют собой две линейные функции времени, вложенные друг в друга. Если в массиве 10 элементов, но вам нужно выполнить итерацию дважды, то n * n = n². Приведенная ниже функция будет вызывать console.log 100 раз для n из 10 и 1 000 000 раз для n из 100!

function printAllPossibleOrderedPairs(items) {
  items.forEach(firstItem => {
    items.forEach(secondItem => {
      console.log(firstItem, secondItem);
    });
  });
}

Логарифмическое время O(log n)

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

Почти все, что выходит за рамки квадратичного времени, в значительной степени не годится. Идея состоит в том, что по мере масштабирования программ, наборов данных и входных данных мы не хотим, чтобы алгоритмы и программы, которые мы пишем, становились неоправданно медленными и утомительными. Иногда решение возможно с использованием алгоритма квадратичного времени, но лучше использовать алгоритм линейного времени.

Это в основном то, что вам нужно знать о нотации Big O! Это ни в коем случае не исчерпывающее объяснение, но его определенно достаточно, чтобы вы начали! Я бы не стал тратить на это слишком много времени, достаточно просто определить, каким может быть алгоритм.

Удачного кодирования!