Wagner Abrantes
Wagner Abrantes12/12/2020 11:48
Compartilhe
Curso Golang Developer
Recomendado para vocêFormação Go Developer

Constantes O(1)

  • #GoLang

Fazemos isso contando as operações, exemplo:

package main

func main() {

}

func constante(n int) int {
  return n * (n + 1) / 2
}

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) .

image

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.

Complexidade Linear:

https://web.digitalinnovation.one/articles/complexidade-linear-on?back=%2Fhome&page=1&order=oldest

Compartilhe
Recomendado para você
  • Curso Flutter Specialist
  • Curso Docker Fundamentals
  • Curso UX Designer
Comentários (0)
He/him Go/Rails Developer writing fun code! Also speak Portuguese, então vi que tava escrevendo em inglês e os artigos em português, imagina ser assim da cabeça.
Recomendado para vocêCurso Golang Developer