# Introdução a algoritmos — Notação Big O

Irei escrever sobre algoritmos e estruturas de dados em paralelo com o livro [Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos](https://www.amazon.com.br/Entendendo-Algoritmos-Ilustrado-Programadores-Curiosos/dp/8575225634/ref=sr_1_1?qid=1677021688&refinements=p_27%3AAditya+Y.+Bhargava&s=books&sr=1-1) de Aditya Y. Bhargava.

Estou usando o livro para aprender sobre algoritmos e estruturas de dados, e escrever sobre o que estou aprendendo, pois acredito que assim eu consiga fixar melhor o conteúdo.

### Capítulo 1 — Introdução a algoritmos

### Notação Big O

A notação Big O é usada para descrever a complexidade de um algoritmo. Ela é usada para descrever o pior caso de um algoritmo, ou seja, o caso em que ele vai demorar mais para ser executado.

Com essa notação, podemos comparar a complexidade de dois algoritmos e dizer qual deles é mais eficiente.

### O que é complexidade de um algoritmo?

A complexidade de um algoritmo é uma medida da quantidade de tempo e espaço que ele usa para executar.

Vale lembrar que a eficiência de um algoritmo não é medida em segundos, mas sim em operações. Por exemplo, se um algoritmo demora 1 segundo para executar, mas usa 10 operações, ele é mais eficiente que um algoritmo que demora 1 segundo para executar, mas usa 1000 operações.

### Exemplos do livro

No livro, o autor dá alguns exemplos de algoritmos e como eles são descritos usando a notação Big O.

Um dos exemplos é o algoritmo de busca linear, usado para procurar um elemento em um array. Ele é descrito como O(n), onde n é o tamanho do array.

Outro exemplo é o algoritmo de busca binária, usado para procurar um elemento em um array ordenado. Ele é descrito como O(log n), onde n é o tamanho do array.

Para saber mais sobre pesquisa binária, veja o meu post sobre o assunto: pesquisa binária.

### Tempo de execução de um algoritmo

O tempo de execução de um algoritmo é a quantidade de tempo que ele leva para ser executado.

Tempo de execução difere de complexidade de um algoritmo. A complexidade de um algoritmo é uma medida da quantidade de tempo e espaço que ele usa para executar. Já o tempo de execução é a quantidade de tempo que ele leva para ser executado.

**O tempo de execução cresce a taxas diferentes para diferentes algoritmos.**

Por exemplo, o tempo de execução de um algoritmo de busca linear cresce linearmente, enquanto o tempo de execução de um algoritmo de busca binária cresce logaritmicamente.

Vamos ver isso em gráficos:

*Gráfico de tempo de execução de um algoritmo de busca linear*

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586271617/92be0db8-3bbc-4d3d-a511-fbf29ea3466d.png)

*Gráfico de tempo de execução de um algoritmo de busca binária*

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586273508/87762087-66fa-4139-85db-df39d3f58c52.png)

Créditos das Imagens: [101computing.net](https://www.101computing.net/wp/wp-content/uploads/Big-O-Notation-Logarithmic-Algorithm.png)

Podemos ver que o tempo de execução de um algoritmo de busca linear cresce linearmente, enquanto o tempo de execução de um algoritmo de busca binária cresce logaritmicamente.

Mas o que isso significa?

Quando falamos que o tempo de execução de um algoritmo cresce linearmente, queremos dizer que o tempo de execução do algoritmo aumenta conforme o tamanho do input.

Vou usar um exemplo do livro para explicar isso.

Em uma lista com 100 elementos, o algoritmo de busca linear vai precisar percorrer todos os 100 elementos para encontrar o elemento que estamos procurando. Já em uma lista com 1000 elementos, o algoritmo de busca linear vai precisar percorrer todos os 1000 elementos para encontrar o elemento que estamos procurando.

Ou seja, o tempo de execução do algoritmo de busca linear cresce linearmente conforme o tamanho do input.

Já quando falamos que o tempo de execução de um algoritmo cresce logaritmicamente, queremos dizer que o tempo de execução do algoritmo aumenta conforme o tamanho do input, mas de forma mais lenta.

Em uma lista com 100 elementos, o algoritmo de busca binária vai precisar percorrer 7 elementos para encontrar o elemento que estamos procurando. Já em uma lista com 1000 elementos, o algoritmo de busca binária vai precisar percorrer 10 elementos para encontrar o elemento que estamos procurando.

Ou seja, o tempo de execução do algoritmo de busca binária cresce logaritmicamente conforme o tamanho do input.

Se formos considerar que leva um 1ms para percorrer um elemento, podemos ver que o algoritmo de busca linear leva 100ms para percorrer uma lista com 100 elementos, enquanto o algoritmo de busca binária leva 7ms para percorrer uma lista com 100 elementos.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586275407/97da26fa-4f4f-4cc7-bc06-3622ee24d11f.png)

Viu como o algoritmo de busca binária é mais eficiente que o algoritmo de busca linear?

### Tipos de algoritmos e suas complexidades

Já vimos dois exemplos de algoritmos e suas complexidades: o algoritmo de busca linear e o algoritmo de busca binária.

O algoritmo de busca linear é descrito como O(n), onde n é o tamanho do array. Já o algoritmo de busca binária é descrito como O(log n), onde n é o tamanho do array.

Vamos ver mais alguns exemplos de algoritmos e suas complexidades:

#### O(1) — Constante

O algoritmo com complexidade O(1) é um algoritmo que sempre vai executar o mesmo número de operações, independente do tamanho do input.

Um exemplo de algoritmo com complexidade O(1) é o algoritmo de busca sequencial, usado para procurar um elemento em um array.

O gráfico abaixo mostra o tempo de execução do algoritmo de busca sequencial:

*Gráfico de tempo de execução de um algoritmo de busca sequencial*

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586276502/7048149e-673c-4bd1-8a6d-2675f35a83a8.png)

Créditos da Imagem: [101computing.net](https://www.101computing.net/wp/wp-content/uploads/Big-O-Notation-Constant-Algorithm.png)

Como podemos ver, o tempo de execução do algoritmo de busca sequencial é constante, independente do tamanho do input.

#### O(n2) — Quadrático

O algoritmo com complexidade O(n2) é um algoritmo que vai executar o número de operações igual ao quadrado do tamanho do input.

Um exemplo de algoritmo com complexidade O(n2) é o algoritmo de ordenação por seleção, usado para ordenar um array.

O gráfico abaixo mostra o tempo de execução do algoritmo de ordenação por seleção:

*Gráfico de tempo de execução de um algoritmo de ordenação por seleção*

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586277826/64f69832-366c-42f7-8a11-77f338de33d5.png)

Créditos da Imagem: [101computing.net](https://www.101computing.net/wp/wp-content/uploads/Big-O-Notation-Polynomial-Algorithm.png)

Como podemos ver, o tempo de execução do algoritmo de ordenação por seleção cresce quadraticamente, ou seja, o tempo de execução do algoritmo de ordenação por seleção é igual ao quadrado do tamanho do input.

#### O(2n) — Exponencial

O algoritmo com complexidade O(2n) é um algoritmo que vai executar o número de operações igual a 2 elevado ao tamanho do input.

Um exemplo de algoritmo com complexidade O(2n) é o algoritmo de busca exaustiva, usado para procurar um elemento em um array.

O gráfico abaixo mostra o tempo de execução do algoritmo de busca exaustiva:

*Gráfico de tempo de execução de um algoritmo de busca exaustiva*

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586279613/246bde59-1338-4ea6-a152-283433dca8f6.png)

Créditos da Imagem: [101computing.net](https://www.101computing.net/wp/wp-content/uploads/Big-O-Notation-Exponential-Algorithm.png)

Como podemos ver, o tempo de execução do algoritmo de busca exaustiva cresce exponencialmente, ou seja, o tempo de execução do algoritmo de busca exaustiva é igual a 2 elevado ao tamanho do input.

### Caixeiro Viajante

Um problema muito comum em algoritmos é o problema do caixeiro viajante, sendo um problema de otimização.

O problema do caixeiro viajante é um problema em que temos um conjunto de cidades e queremos encontrar a rota mais curta para visitar todas as cidades uma única vez e voltar para a cidade de origem.

Vamos ver um exemplo de problema do caixeiro viajante:

*Problema do caixeiro viajante*

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586281378/c5942f67-3389-4505-b054-ccb0f0c3c8fd.jpeg)

Créditos da Imagem: [optimoroute.com](https://optimoroute.com/wp-content/uploads/2020/07/Traveling-salesman-problem3.jpg)

Como podemos ver, temos um conjunto de cidades e queremos encontrar a rota mais curta para visitar todas as cidades uma única vez e voltar para a cidade de origem.

Uma solução para esse problema seria percorrer todas as cidades e calcular a distância entre elas, e depois escolher a rota com a menor distância.

Seguindo do princípio que teríamos somente 5 cidades, teríamos 5! = 120 combinações possíveis de rotas.

Mas se tivéssemos 6 cidades, teríamos 6! = 720 combinações possíveis de rotas.

Esse problema é chamado de problema de otimização combinatória, pois temos um conjunto de combinações possíveis e queremos encontrar a melhor combinação.

Segue a tabela com o número de combinações possíveis para cada número de cidades:

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586282742/e3d5cef4-d140-4c58-856c-14d14d6180bd.png)

Como podemos ver, o número de combinações possíveis cresce exponencialmente, ou seja, o número de combinações possíveis é igual a 2 elevado ao número de cidades.

Como o número de combinações possíveis cresce exponencialmente, não é possível calcular todas as combinações possíveis para um número grande de cidades.

Esse problema é chamado de problema NP-Completo, sendo um problema que não é possível calcular todas as combinações possíveis.

Dessa forma, não é possível encontrar a melhor solução para esse problema, mas podemos encontrar uma solução aproximada para esse problema.

Deixei esse problema para o final, por ser um problema que é muito comum em algoritmos e gera muita curiosidade pela sua complexidade.

### Finalização

Essa foi uma pequena documentação dos meus estudos, espero que possa ajudar mais pessoas.  
Qualquer dúvida, correção ou sugestão pode deixar nos comentários.