Complexidade Linear O(n)
- #GoLang
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”.
Complexidade Logarítmica:
