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

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

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

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)

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.

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.