Как рассчитать нотацию big o?

Что такое нотация Big O?

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

Что такое временная сложность?

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

Вы можете ознакомиться с различными временными сложностями в таблице ниже:

Здесь вы можете увидеть обозначение общих функций в виде большой буквы o.

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

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

Вы можете посмотреть некоторые примеры временных сложностей циклов.

//O(n)
for(let i=0; i<n; i++){

}

//O(n*m) --> O(n²)
for(let i=0; i<n; i++){
    for(let j=0; j<m; j++){

    }
}

let s = 0; //O(1)


//O(log(n))
for(let i=n; i>0; i=i/2){

}

Когда мы смотрим примеры графов в калькуляторе Desmos, мы получаем лучшее представление о том, как алгоритмы могут масштабироваться. И это относится не только к алгоритмам, мы можем использовать эти знания для запросов к базам данных. Например, если у нас есть таблица без определенного индекса, то временная сложность поиска будет равна O(n). Но если мы определим индекс, то временная сложность поиска составит O(log(n)). Поскольку при создании индекса нам не нужно проверять каждую строку в таблице, вместо этого мы можем использовать алгоритм «разделяй и властвуй», осуществляя поиск по индексу.

Вычисление

Давайте посмотрим, как можно вычислить алгоритм в нотации big o.

let sum = (n) => {
    let res = 0 // O(1)
    for(let i=0; i<n; i++){ //O(n)
        res += i // O(1)
    }
    return res // O(1)
}

Суммируя все временные сложности, мы получаем O(n).

sum = 1 + n*1 + 1 = n + 2 => O(n)

Пример для временной сложности n*log(n)

let sumDivide = (n) => {
    let res = 0 // O(1)
    for(let i=n; i<n; i/2){ //O(log(n))
        for(let j=n; j<n; j/2){ //O(n)
            res += j // O(1)
        }
    }
    return res // O(1)
}

sumDivide = 1 + log(n)*n*1 + 1 = n*log(n) + 2 => O(n*log(n))