Complexidade de Algoritmo com Big'O.
Tags: notation, estude, dev, python
Published: 2021-12-23 03:36:12

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.

```python
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:

```python
# 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:

```python
# 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](https://jarednielsen.com/big-o/), resultando em:

```python
# 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.

![Função linear](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/grc06jdt1intd6o73cmr.jpg)

Este foi o <b>diário de bordo #13</b>. 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.

<p align="center">
  <a href="#">
    <img src="https://cdn.dribbble.com/users/1889486/screenshots/5081642/thankyou_.gif" width="500">
  </a>
</p>

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

## Referências 

* [Notação do O Grande - Complexidade de Algoritmos II](https://www.youtube.com/watch?v=UQzCFkRbIrE) 
* [The Superlative Guide to Big O](https://jarednielsen.com/big-o/)