Complexidade Linear O(n)

Toda complexidade diferente da constante se da em relação ao numero de itens que a sua função recebe, então quanto maior o input maior o tempo de execução do algoritmo. Só que na complexidade linear a diferença é bem proporcional ao tamanho da entrada, ao invés de ser gritante.

Em Big O Notation, complexidade linear é apresentada como O(n). Algoritmos de String matching, como Boyer-Moore (usando a regra de Galil) e Ukkonen tem complexidade linear.

Mas a questão toda não é pegar os algoritmos conhecidos e procurar no Google a complexidade deles e sim enxergar os padrões nesses algoritmos e entender a ponto de flagrar a complexidade no seu código e de outras pessoas. A pergunta a ser feita não é “esse algoritmo é O(n)?” e sim “O porquê desse algoritmo ser O(n)?”.

Se chegar ao final e conseguir responder essa ultima pergunta, você começou a entender Big O Notation.

A complexidade linear,O(n), é demonstrada em um algoritmo da seguinte forma:

package main

import (
    "fmt"
)

func linear(n int) int {
    total := 0
    for i := 1; i <= n; i++ {
        total++
    }
    return total
}

func main() {
    fmt.Println(linear(10))
}

Aqui temos uma operação apenas e não três como anteriormente, nesse caso é total ++ que é o mesmo que: total é igual a total + 1, porém a complexidade é totalmente diferente pois o input também define quantas vezes i será incrementado no for statement. Então quanto maior for o input_(n)_ maior o numero de operações serão feitas em total.

Se no lugar de (i <= n) eu colocasse (i <= 10) seria um tempo constante O(1) mas como o input interfere no for essa complexidade é O(n).

Se formos olhar cada pedaço e dizer o número de operações:

• total := 0 (Uma operação)
• i := 0 (Uma operação)
• i++(N operações)
• total ++( N operações)

Quando for analisar a complexidade do algoritmo não é necessário contar todas as operações, na maioria das vezes você vai acabar percebendo. Nesse caso como temos operações que são relacionadas a N que é o numero de inputs não tem porque nos preocuparmos com as que são constantes pois a parte linear já dominará a notação de complexidade, então se a gente deixar as constantes de lado sobram apenas as O(n).

E se você tiver dois for statement? Tipo assim:

package main

import "fmt"

func elevador(n) {
    for i := 0 ; i < n; i++{
        fmt.Println(i)
    }

    for j := n - 1 ; j >= 0; j--{
        fmt.Println(j)
    }
}

Ainda assim a complexidade será O(n) e não O(2n) porque Big O é sobre o comportamento quando a entrada cresce muuuuito. Lá perto do infinito e além pouco importa se é n ou 2n.

Pode ser que eu esteja batendo na mesma tecla, porém recomendo que leia mesmo as partes que você considera que já sabe. O maior perigo de aprender é achar que já entendeu e não precisa estudar mais.

Agora temos em perspectiva dois tipos de complexidade a constante em cinza e a linear em azul e agora fica muito óbvio o porque do nome. Repare que dessa vez o input é de 10gb e não 10tb se eu tentasse fazer com um input de 10tb em um algoritmo de complexidade O(n) levaria bem mais tempo. A linha de O(1) permanece plana não leva nem 1 segundo de runtime, a azul com um input de 10gb já leva 18 segundos.

Eu não to falando pra você ficar contando segundo, isso vai depender do seu cenário, mas se você olhar o quanto as linhas já se distanciaram é bastante e como diz o ditado “de grão em grão a galinha enche o papo”.