Os Fundamentos da Notação Big-O
Tags: beginners, programming, algorithms, braziliandevs
Published: 2022-09-24 01:05:43


## Como utilizar a notação Big-O para medir o desempenho e a escalabilidade do seu algoritmo

_Foto de [Nadine Shaabana](https://unsplash.com/@nadineshaabana?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) no [Unsplash](https://unsplash.com/s/photos/light?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)_

Na era em que os dados crescem cada vez mais, não é mais suficiente criar um algoritmo que "simplesmente funcione" para resolver o problema. Não importa qual seja sua profissão, seja desenvolvedor de software, cientista de dados ou engenheiro de aprendizado de máquina, a capacidade de criar um algoritmo eficiente e escalável é uma habilidade altamente desejável.

Para criar um algoritmo eficiente, na maioria das vezes precisamos pensar fora da caixa para ter uma idéia de como otimizar o desempenho do código. E quando tentamos otimizar o código, às vezes não sabemos como medir a eficiência do nosso algoritmo — se ele foi melhorado ou não.

Neste post, vamos falar sobre como você pode medir o desempenho do seu algoritmo utilizando a notação Big-O.

---

# Maneira correta de medir o desempenho de um algoritmo

Antes de tudo, vamos pensar por um momento: como sabemos que nosso algoritmo é bom ou eficiente? como medimos o desempenho do nosso algoritmo? Provavelmente, a maneira mais fácil de medir o desempenho do algoritmo é medindo o tempo necessário para calcular a solução.

No entanto, medir a duração do tempo não é uma ótima maneira de avaliar o desempenho do seu algoritmo porque:

- O computador que estamos usando terá um enorme impacto na rapidez com que o algoritmo é executado. Se você estiver usando um hardware antigo, é esperado que o código seja executado mais lentamente do que se estivesse usando um hardware mais novo.
- Se você executar o algoritmo enquanto outros programas se encontram abertos e ativos em seu computador, o tempo necessário para que seu algoritmo resolva a solução será mais lento do que se seu computador dedicasse todos os seus recursos para executar o algoritmo.
- O compilador e as bibliotecas que usamos em nosso algoritmo também afetam sua duração de tempo de execução.

Portanto, deve haver uma maneira melhor de medir o desempenho do algoritmo.

Ao invés de focar na duração do tempo para executar seu algoritmo, precisamos nos concentrar mais na escalabilidade ou complexidade do tempo de execução do nosso algoritmo: como o desempenho do nosso algoritmo muda à medida que o tamanho da entrada aumenta?

Para medir a complexidade do tempo de execução do nosso algoritmo, insira o conceito por trás da notação Big-O.

---

# A notação Big-O

A notação Big-O é o termo que você costuma ouvir em Ciência da Computação quando fala sobre eficiência de algoritmo. Mas, o que significa a notação Big-O?

> Em termos simples, a notação Big-O descreve quão bom é o desempenho do seu algoritmo à medida que os dados de entrada crescem.

Com a notação Big-O, podemos medir a escalabilidade do nosso algoritmo: nosso algoritmo ainda terá um bom desempenho à medida que a entrada cresce?

Neste post vamos falar sobre quatro das notações Big-O mais comuns: 

- **O(1)**
- **O(n)**
- **O(n²)**
- **O(log n)** 

Esses **_Os_** significam **_Order Of_** , então **O(n)** significa **_Order Of n_** , onde **_n_** é o tamanho dos dados de entrada. 

Vamos analisar essas notações uma por uma.

---

## O(1) — Complexidade de tempo de execução constante

A notação **O(1)** significa que seu algoritmo tem uma complexidade de tempo de execução constante porque leva o mesmo número de operações, independentemente do tamanho dos dados de entrada.

Para torná-lo mais intuitivo, vamos dar uma olhada no trecho de código abaixo.

```python
def array_elements(array):
  print(array[0])
```

O trecho de código acima é o exemplo simples de um algoritmo com notação **O(1) .** A função recebe um array e exibe o primeiro elemento do array. Não importa quantos elementos existam no array, esta função sempre será executada em um tempo de execução constante porque seu trabalho é apenas exibir o primeiro elemento do array.

Vamos dar uma olhada em outro algoritmo que tem complexidade de tempo **O(1) .**

```python
def array_elements(array):
  third_index = array[2]
  return third_index
```

No trecho de código acima, a função recebe um array e seu trabalho é atribuir o terceiro elemento do array a uma variável chamada `third_index`. Novamente, não importa quão grande seja o tamanho da matriz de entrada, a função sempre será executada em um tempo de execução constante porque seu único trabalho é atribuir o valor do terceiro elemento da matriz a uma variável.

Agora, se plotarmos a complexidade de tempo do algoritmo com notação **O(1) com o tamanho dos dados de entrada, obteremos o seguinte gráfico.**

![Complexidade de tempo do algoritmo com notação O(1)](https://miro.medium.com/max/640/1*C--4xOJ1aDuUykTZ4z5UGg.png)

Como você pode ver, a complexidade do tempo de execução do algoritmo permanece constante à medida que os dados de entrada crescem cada vez mais.

---

## O(n) — Complexidade de tempo de execução linear

A notação **O(n)** significa que a complexidade do tempo de execução do seu algoritmo tem uma relação linear com o tamanho dos dados de entrada. Se o tamanho dos dados de entrada for aumentado em 2, a complexidade do tempo de execução do seu algoritmo também será aumentada em 2.

Vamos dar uma olhada no trecho de código abaixo para torná-lo mais intuitivo.

```python
def array_element(array):
  for i in range (len(array)):
  print(array[i])
```

Ter um loop iterando sobre os elementos de um array e imprimindo o valor de cada um de seus elementos é o exemplo perfeito de um algoritmo que possui notação **O(n) .**

No trecho de código acima, o custo do nosso algoritmo muda em relação ao tamanho do array de entrada. Se a matriz de entrada tiver apenas 2 elementos, nosso algoritmo levará apenas 2 operações para ser executado. Se a matriz tiver 100 elementos, o algoritmo também levará 100 operações para ser executado. Em outras palavras, o custo do nosso algoritmo aumenta linearmente com o tamanho do array de entrada.

Agora, se plotarmos a complexidade do tempo de execução com o tamanho dos dados de entrada, obteremos o seguinte gráfico.

![Complexidade de tempo do algoritmo com notação O(n)](https://miro.medium.com/max/640/1*X5JanH7K1HPOarB4fJpTTg.png)

Como você pode ver, temos uma relação linear entre a complexidade do tempo de execução e o tamanho dos dados de entrada. Quanto mais elementos houver na matriz de entrada, mais operações serão necessárias para que nosso algoritmo seja executado.

---

## O(n²) — Complexidade de tempo de execução quadrática

A notação **O(n²)** significa que a complexidade do tempo de execução do seu algoritmo é proporcional ao quadrado do tamanho da entrada. Digamos que o tamanho de entrada do seu array seja 3, então a complexidade do tempo de execução do seu algoritmo será aumentada em 9.

Vamos dar uma olhada no trecho de código abaixo como exemplo de algoritmo com complexidade **O(n²)** .

```python
def array_element(array):
  sum_number = 0
  for i in range (len(array)):
    for j in range (len(array)):
      sum_number += array[i]+array[j]
  return sum_number
```

Loops aninhados são o exemplo perfeito de um algoritmo com notação **O(n²) .** Isso ocorre porque o loop está iterando sobre cada elemento de uma matriz duas vezes. O loop interno tem a complexidade de **O(n)** , e o loop externo também tem a complexidade de **O(n)** . Agora, se combinarmos a complexidade entre o loop interno e o loop externo, obtemos a complexidade de **O(n²)** .

Digamos que o tamanho do nosso array de entrada seja 3. Para loop externo, são necessárias no total 3 operações para iterar sobre cada elemento de um array. Para cada uma dessas 3 operações, também são necessárias 3 operações para fazer o loop interno para iterar sobre cada elemento. Isso leva a 9 operações no total.

Se traçarmos o gráfico, você obterá a seguinte visualização para um algoritmo com complexidade **O(n²)** .

![Complexidade de tempo do algoritmo com notação O(n²)](https://miro.medium.com/max/640/1*GKAnOWbIA7CRV4OUB3STZw.png)

Como podemos ver, o custo do nosso algoritmo será muito mais caro à medida que o tamanho dos nossos dados de entrada for aumentado.

---

## O(log n) — Complexidade logarítmica de tempo de execução

A próxima complexidade de tempo de execução que devemos conhecer é **O(log n)** . Essa notação significa que a complexidade do tempo de execução do seu algoritmo **será aumentada em um quando o tamanho dos dados de entrada forem duplicados**.

Vamos dar uma olhada no trecho de código abaixo como exemplo.

```python
def binary_search(array, value):
    
    first_val = 0
    last_val = len(array)-1
    bool_stat = False
    
    while (first_val <= last_val and bool_stat == False):
 
        mid_val = (first_val + last_val) // 2
        
        if array[mid_val] == value:
           bool_stat = True
           return bool_stat
       
        elif value > array[mid_val]:
           first_val = mid_val + 1 
           
        else:
           last_val = mid_val - 1
           
    return bool_stat

array = [1,2,3,4,5,6,7,8,9]
value = 7

is_found = binary_search(array, value)
```

O trecho de código acima é o algoritmo de busca binária que tem uma complexidade de tempo de execução de **O(log n)** . Em vez de iterar sobre cada elemento de uma matriz com loop _for_ , a pesquisa binária sempre dividirá recursivamente o tamanho dos dados de entrada pela metade para encontrar o valor desejado.

Conforme mostrado no código acima, temos um array com tamanho de entrada 9. Supondo que os dados estejam perfeitamente ordenados, nosso objetivo é descobrir se o valor de 7 existe neste array. A busca binária primeiro dividirá o array de entrada ao meio e verificará o valor no meio do nosso array.

![](https://miro.medium.com/max/720/1*oM1WR0WzjNA8vzB7L2AE0w.png)

Como o valor no meio do nosso array é 5, esse valor será então verificado com o valor que estamos procurando, que neste caso é 7. Como 5 é menor que 7, então o algoritmo usará os valores em do lado direito da matriz, que são de 6 a 9.

![](https://miro.medium.com/max/720/1*7NXfh315QIJLVHFyHGVgew.png)

Agora o tamanho de entrada do nosso array é 4 em vez de 10. O novo array então será dividido novamente pela metade, o que nos deixa com um array com um valor de 6 e 7 e um array com um valor de 8 e 9.

Como o valor de 7 está na matriz de 6 e 7, o algoritmo usará essa parte de uma matriz e ignorará a matriz com o valor de 8 e 9.

![](https://miro.medium.com/max/720/1*vLx-JlUFs8QTq4ztaCCWig.png)

Até que finalmente encontramos o valor que queremos, que é 7.

Se desenharmos o gráfico do algoritmo com a complexidade de tempo de execução de **O(log n)** , obteremos a seguinte visualização.

![Complexidade de tempo do algoritmo com notação O(log n)](https://miro.medium.com/max/640/1*UHTWeGAoDrJL1mhvtKkVGw.png)

Como você pode ver, o algoritmo que tem notação **O(log n)** é mais escalável que **O(n)** e **O(n²)** à medida que o tamanho da entrada cresce cada vez mais.

Em nosso exemplo acima, se usarmos o loop _for_ , que tem uma notação linear **O(n)** , nosso algoritmo precisará de 7 operações antes de encontrar uma solução (já que estamos procurando o valor 7). Enquanto isso, com o algoritmo de busca binária, que tem notação **O(log n)** , são necessárias apenas 4 operações para resolver o problema.

---

## Comparações de complexidade entre diferentes notações Big-O

Vamos recapitular um pouco sobre as diferentes notações Big-O que aprendemos até agora em termos de escalabilidade. Abaixo está o gráfico dessas notações Big-O.

![Todas notações Big-O](https://miro.medium.com/max/640/1*Qy_Z4Og2L1Bxn0gNroflqw.png)

Como você pode ver, o algoritmo com notação **O(1)** tem a melhor escalabilidade à medida que o tamanho da entrada cresce cada vez mais, enquanto o algoritmo com notação **O(n²)** tem a pior escalabilidade entre todos.

Para resumir, abaixo está a ordem de escalabilidade da notação Big-O iniciada do melhor para o pior:

```
**O(1) < O(log n) < O(n) < O(n^2)**
```

---

# Determinando a notação Big-O de um código

Agora que conhecemos diferentes tipos de notação Big-O, vamos tentar descobrir a complexidade de tempo de execução de um código. Quando tentamos analisar a complexidade de tempo de execução de um código, sempre temos que enfrentar dois cenários diferentes: o melhor cenário e o pior cenário.

---

## Melhor cenário e pior cenário

Para facilitar o entendimento da diferença entre o melhor cenário e o pior cenário, vamos dar uma olhada no trecho de código abaixo:

```python
def linear_search(array, value):
    
    for i in range (len(array)):
        
        if array[i] == value:
            
           return True
       
    return False

def binary_search(array, value):
    
    first_val = 0
    last_val = len(array)-1
    bool_stat = False
    
    while (first_val <= last_val and bool_stat == False):
 
        mid_val = (first_val + last_val) // 2
        
        if array[mid_val] == value:
           bool_stat = True
           return bool_stat
          
        elif value > array[mid_val]:
           first_val = mid_val + 1 
           
        else:
           last_val = mid_val - 1
           
    return bool_stat

array = [1,2,3,4,5,6,7,8,9]
value = 7
```

No trecho de código acima, temos um algoritmo para pesquisa linear (iterando os elementos de cada array com loop _for ) e um para pesquisa binária (dividindo recursivamente o array)._ Digamos que temos um array perfeitamente ordenado com 9 elementos como você pode ver acima.

-   O melhor caso para pesquisa linear seria se quisermos pesquisar o valor de 1, que é o primeiro elemento da matriz. Neste caso, temos complexidade **O(1) .**
-   O pior caso para pesquisa linear seria se quisermos pesquisar o valor de 9, que é o último elemento do array, ou se quisermos pesquisar um valor que não esteja incluído no array. Isso ocorre porque o algoritmo precisa percorrer cada elemento da matriz. Neste caso, temos complexidade **O(n) .**
-   O melhor caso para pesquisa binária seria se quiséssemos pesquisar o valor de 5, que é o valor no elemento do meio da matriz. Neste caso, temos complexidade **O(1) .**
-   O pior caso para a busca binária seria se quiséssemos buscar o valor de 1 ou 10, que são o primeiro e o último elemento do array, ou o valor que não está incluído no array. Isso ocorre porque com a busca binária, o algoritmo precisa dividir os dados ao meio recursivamente até atingir o primeiro e o último elemento. Neste caso, temos a complexidade de **O(log n)**.

![](https://miro.medium.com/max/720/1*CFS6q3ClcpHU05reRoCxXg.png)

## Estimando a notação Big-O de um código

Quando se trata de determinar a notação Big-O de um código, precisamos sempre olhar para a perspectiva do pior cenário. Agora com esse conceito em mente, vamos tentar estimar a notação Big-O de um código.

Vamos dar uma olhada no trecho de código abaixo e vamos verificar sua complexidade.

```python
def max_value(array):
    
    value = 0  # O(1) complexity
    
    for i in range (len(array)): # O(n) complexity
    
        for j in range (len(array)-10): # O(10) complexity
        
            for k in range (len(array)//2): # O(n/2) complexity
                
                value += array[i] + array[j] + array[k] # O(1) complexity
                
    return value # O(1) complexity
```

Ao estimar a notação Big-O de um código, precisamos sempre observar primeiro a operação no loop mais interno. Abaixo segue o passo a passo de como devemos investigar a complexidade do Big-O do código acima:

1.  A partir da operação no loop mais interno, que é `value += array[i] + array[j] + array[k]`. Esta operação tem uma complexidade **O(1) constante.**
2.  Em seguida, olhamos para o loop mais interno, que é `for k in range (len(array)/2)`. Esse loop sempre iterará mais da metade do tamanho do nosso array, portanto, tem complexidade **O(n/2) .**
3.  Em seguida, subimos um nível, que é o loop `for j in range (len(array)-10)`. Embora este seja um loop _for_ , mas tem uma complexidade de tempo de execução constante. Isso ocorre porque não importa quão grande seja o tamanho da matriz de entrada, esse loop sempre iterará apenas nos últimos 10 elementos. Portanto, tem uma complexidade **O(10) constante.**
4.  Em seguida, passamos para o loop externo, que é `for i in range (len(array))`. Este loop _for_ sempre iterará sobre o tamanho da matriz de entrada. Portanto, esse loop tem complexidade **O(n) .**
5.  Finalmente, passamos para as operações fora do loop, que são `value = 0`e `return value`. Essas duas operações sempre serão executadas em um tempo de execução constante, portanto, ambas têm complexidade **O(1) .**

Agora que analisamos a notação Big-O de todos os loops e operações, a seguir vamos analisar a notação Big-O de todo o código. Para fazer isso, também precisamos sempre começar do loop mais interno.

1.  O loop mais interno tem complexidade **O(n/2)** e a operação neste loop tem complexidade **O(1)** . Isso significa que esse loop mais interno tem complexidade.`(n/2)*(1) =  **O(n/2)**`
2.  Em seguida, o segundo loop interno tem complexidade **O(10) .** O loop interno deste loop, como computamos no ponto nº 1, tem **O(n/2)** . Isso significa que o segundo loop interno tem complexidade.`10*(n/2) =  **O(5n)**`
3.  Finalmente, o loop externo tem complexidade **O(n) .** O loop interno deste loop externo tem uma complexidade total de **O(5n)** , conforme computamos no ponto no.2. Então, no total, eles têm complexidade.`n*5n =  **O(5n^2)**`
4.  Se combinarmos a complexidade do loop e as duas operações fora do loop, obtemos . Como você pode ver, o código acima no total tem complexidade **O(2+5n²)** .`1+1+5n^2 =  **O(2+5n^2)**`

Quando estamos estimando a notação Big-O de um código, podemos simplificá-la eliminando todas as constantes. Então, em vez de **O(2+5n²)** , podemos descartar todas as constantes e ficar com **O(n²)** . Portanto, o código acima tem complexidade **O(n²)** .

---

E é isso por enquanto!

Espero que agora você saiba como medir e estimar o desempenho de um algoritmo observando sua notação Big-O. Projetar um algoritmo escalável é muito benéfico para otimizar o código à medida que os dados de entrada crescem cada vez mais a cada dia.

# Créditos

- [The Fundamentals of the Big-O Notation](https://towardsdatascience.com/the-fundamentals-of-the-big-o-notation-7fe14210b675), escrito originalmente por [Ruben Winastwan](https://medium.com/@marcellusruben).