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

Omega представляет лучший случай, Theta — средний случай, а Omicron (Big O ) наихудший случай.Большая О всегда измеряет наихудший случай.

Предположим, у нас есть два фрагмента кода, и оба достигают одного и того же. Как нам решить, какой из них лучше? Big O – это способ математически понять это, помогая нам определить, какой код более эффективен.

Big O понимает это двояко:

  1. Временная сложность: масштабирование в зависимости от количества операций.
  2. Пространственная сложность: объем памяти, который что-то использует.

Сразу покажу на примере.

function logElements(n) {
    for(let i = 0; i < n; i++) {
        console.log(i)
    }
}

logElements(4)

Мы передали функции число n, и она выполнялась n раз. В примере мы прошли 10, и он запустился 10 раз. По этой причине результат равен O(n)

Есть несколько способов упростить Big O, и один из них — Отбросить константы. Давайте попробуем это на примере, который включает цикл for.

function logElements(n) {
     for(let i = 0; i < n; i++) {
        console.log(i) 
     }
 
     for(let j = 0; j < n; j++) {
        console.log(j) 
     }       
 }
 
 logElements(4)

Вывод: 0, 1, 2, 3 для первого цикла и 0, 1, 2, 3 для второго цикла.

2н, 5н, 400н. Начальные константы не имеют значения. Если есть константа, мы ее отбрасываем, и результат становится O(n)

Давайте попробуем решить пример, который включает в себя цикл for внутри цикла for.

function logElements(n) {
     for(let i = 0; i < n; i++) {
         for(let j = 0; j < n; j++) {
             console.log(i, j) 
         }       
     } 
 }
 
 logElements(4)

Вывод начинается с 0 0, 1 1, … и останавливается, когда достигает 3 3.

Решение для большого О — n*n, поэтому это n2. Результат: O(n2).

Отбросить недоминирующие элементы – это еще один способ упростить Big O.

function logElements(n) {
     for(let i = 0; i < n; i++) {
         for(let j = 0; j < n; j++) {
             console.log(i, j) 
         }       
     } 
 
     for(let k = 0; k < n; k++) {
         console.log(k)
     }
 }
 
 logElements(4)

n2 здесь будет любым числом. Например, это будет 100000, поэтому n не может существенно повлиять на результат.

Давайте приведем несколько примеров с разными результатами.

function manyItems(n) {
  return n+n+n+n
}

Будь то n+n+n+…+n или просто n+n, результат не изменится. Большой О — это О(1). O(1) представляет собой постоянное время.

На данный момент мы только коснулись основ; Подробнее я расскажу в своих следующих статьях. Я не все упомянул в этой статье, потому что некоторые темы сложны. Наконец, я включил сюда график эффективности Big O. До встречи в следующих статьях.