DEV Community

Cover image for Complexidade de Algoritmo com Big'O.
Suspir0n
Suspir0n

Posted on

Complexidade de Algoritmo com Big'O.

Olá galera, hoje eu vim falar sobre complexidade de algoritmo, especificamente sobre a notação do O grande, conhecido como Big'O notation.

Sabemos que uma complexidade é uma medida da quantidade de recursos que o algoritmo precisa para executar no computador, nele temos a complexidade de tempo e a complexidade de espaço, caso não especificarmos de qual complexidade se trata, significa que estamos falando da complexidade de tempo.

Para verificamos a eficiência de um código, precisamos analisar a complexidade do mesmo, estarei utilizando um exemplo simples de inversão de lista para poder explicar melhor. Lembrando que cada computador executa no seu tempo, por isso estaremos analisando a entrada e o comportamento da função.

def inverter_lista(lista):
    tamanho = len(lista)
    limite = tamanho//2
    for i in range(limite):
        aux = lista[i]
        lista[i] = lista[n-i]
        lista[tamanho-i] = aux
Enter fullscreen mode Exit fullscreen mode

Analisando o código acima, começaremos a verificar a complexidade de espaço, o mesmo retrata sobre as variáveis, no caso, o espaço na memória que elas estão sendo alocadas, logo ficaria assim:

# 4 + N = complexidade de espaço
Enter fullscreen mode Exit fullscreen mode

Porque 4? Porque temos quatro variáveis, a tamanho, limite, aux e i. O N seria a lista, pois não sabemos o tamanho dela, logo pode ser N valores.

Após termos verificado a complexidade de espaço, agora iremos verificar a de tempo, por cada linha na função que será executada, logo ficaria desta forma:

# 2 + 4*(N/2) = complexidade de tempo
Enter fullscreen mode Exit fullscreen mode

Nele podemos observar:

  • 2 - são às duas primeiras linhas que são executadas antes do for
  • 4 - são as quatro linhas que serão executadas dentro do for
  • (N/2) - é o valor limite

Podemos ainda simplificar esta equação, se você analisar, só estamos utilizando a variável aux e a lista e se dividimos N/2 o resultado será N, logo a equação ficaria 2 + 2*N.

Certo, a equação 2 + 2*N, o 2 faz diferença quando o tamanho da lista é pequena, por exemplo, se a lista tiver o tamanho de 4 elementos, substituindo o N na equação pelo 4, ficaria 2 + 2*4 resultando em 2 + 8 -> 10, você percebe que a diferença que ela faz é de 20% na utilização de recursos, mais se com o tempo formos aumentando a quantidade de elementos na lista, por exemplo, 100, na equação ficaria 2 + 2*100 -> 2 + 200 -> 202, logo você percebe que com este valor o 2 teria uma diferença de 1% na utilização de recursos e assim por diante. Chegamos a conclusão que o dominante na equação que é o 2*N, nele que iremos saber o quanto de utilização de recursos estará sendo usado em maior parte.

Próximo passo para chegarmos na notação que queremos, temos que remover da equação tudo aquilo que não é dominante, o que já fizemos anteriormente.

Logo este 2*N também chegará a não ser mas irrelevante não é mesmo? Até porque sabemos que, o que define nesta equação é o valor de N logo para definimos isso usaremos a notação do Big'O, resultando em:

# 2*N - complexidade de tempo = O(n)
Enter fullscreen mode Exit fullscreen mode

O O(N), ela expressa um conjunto de funções dominadas pelo termo de grau N.

Mas fizemos aquela analise e aquela equação toda para ficarmos apenas com este termo, esse N? Sim, para analisar o algoritmo, tivemos que entender como funcionava, como era seu comportamento em si, qual o crescimento dele conforme a entrada, no caso a lista. Logo precisamos saber se ele é um conjunto de função que pertence ao O(n). Entretanto, podemos dizer que o gráfico desta função é linear, pois vai crescendo conforme o tamanho da entrada.

Função linear

Este foi o diário de bordo #13. Hoje eu escolhi falar sobre o Big'O Notation na próxima semana irei trazer sobre o SoC galera, vlw. Vamos nos despedindo por aqui. Voltaremos com mais um diário de bordo.

Este artigo foi útil para você?
Deixe um comentário abaixo.

Referências

Top comments (0)