Constantes O(1)

vapordev

Wagner Abrantes

Posted on October 15, 2020

Constantes O(1)

Fazemos isso contando as operações, exemplo:

package main

func main() {

}

func constante(n int) int {
    return n * (n + 1) / 2
}
Enter fullscreen mode Exit fullscreen mode

Aqui temos, uma multiplicação, uma adição e uma divisão. três operações.

E ai não importa se N é 2 ou 1 bilhão, o numero de operações é o mesmo, três! Essa é uma complexidade de O(3) é um tipo de complexidade constante pois o numero de operações não muda mesmo que o input seja diferente.

Só que, em Big O a notação tem regras onde você não precisa ficar somando cada operação, O(3) ou O(200) no final tempo constante é sempre O(1).

Geralmente se ignora as constantes em um algoritmo, por que a notação big O se importa com o comportamento do algoritmo à medida que a entrada cresce muito, e não com os detalhes exatos pra todos os tamanhos. Quanto maior a entrada fica, menos importante as constantes vão se tornando. Por isso todo algoritmo com número de operações constante tem tempo de execução em O(1) .

Nesse gráfico fica bem explicito o como uma complexidade constante se comporta, no eixo vertical temos a relação de tempo e horizontal a de N (input) temos um ultimo input de 10tb sobre esse algoritmo do exemplo e nessa simulação ele não leva nem um milésimo de execução. Mais a frente olharemos o mesmo gráfico em perspectiva a diferentes complexidades.

💖 💪 🙅 🚩
vapordev
Wagner Abrantes

Posted on October 15, 2020

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

Constantes O(1)
bigonotation Constantes O(1)

October 15, 2020