Compreendendo a Notação Big O: Medindo a Eficiência dos Algoritmos
Tags: notaçãobigo, eficiênciaalgorítmica, desenvolvimentodesoftware
Published: 2023-07-01 14:02:57

Hoje, vamos falar sobre um conceito fundamental em ciência da computação e análise de algoritmos: a notação Big O. Se você já teve contato com programação ou estudos relacionados, provavelmente já ouviu falar sobre esse termo. Mas o que exatamente ele significa e por que é tão importante? Vamos descobrir juntos!

A **_notação Big O_** é uma forma de descrever a complexidade de um algoritmo, ou seja, a medida de quanta memória ou tempo computacional ele requer à medida que o tamanho da entrada aumenta. É uma ferramenta essencial para analisar e comparar algoritmos, permitindo-nos escolher a melhor solução para um determinado problema.

_"A notação Big O é uma notação matemática que descreve o comportamento limitante de uma função quando o argumento tende a um valor específico ou ao infinito. Ela pertence a uma família de notações inventadas por Paul Bachmann, Edmund Landau e outros, coletivamente chamadas de notação Bachmann–Landau ou de notação assintótica."_ **— Definição da Wikipédia de notação Big O**

Ao utilizar a **_notação Big O_**, expressamos a eficiência de um algoritmo em termos de seu crescimento assintótico. Em outras palavras, estamos interessados no comportamento do algoritmo quando a quantidade de dados aumenta consideravelmente. A notação Big O nos permite identificar o crescimento mais significativo em relação ao tamanho da entrada e descrevê-lo de forma simplificada.

Você pode perguntar: mas quem liga para isso?. Bem, acontece que você frequentemente utilizará o algoritmo feitos por outras pessoas, e quando faz isso, é bom entender o quão rápido ou lento o algoritmo é. 

Para exemplificar o que é a **_notação Big O_**, vamos dar uma olhada em um caso típico, _**O(n²)**_, que geralmente é chamada também de _**"Big O quadrática"**_. A letra **_n_** representa o tamanho da entrada, enquanto a função "**_g(n) = n²"_** interna ao **_"O()"_** nos dá a ideia da complexidade do algoritmo em relação ao tamanho da entrada.

Outro exemplo é da _**pesquisa binária**_, que precisa de _**log n**_ operações para verificar uma lista de tamanho **_n_**. A complexidade desse algoritmo é da ordem de **_O(log2 n)_**, em que **_n_** é o tamanho do vetor de busca. 

**Vamos examinar alguns exemplos comuns de notações Big O:**

- O(1): Tempo de execução constante: Independentemente do tamanho da entrada, o algoritmo sempre leva o mesmo tempo para ser executado. É o cenário ideal, onde a eficiência não é afetada pelo aumento dos dados.

- O(log n): Tempo de execução logarítmico: O tempo de execução aumenta de forma logarítmica à medida que o tamanho da entrada aumenta. Algoritmos com essa complexidade são geralmente muito eficientes, como é o caso de **_árvores balanceadas_** e algoritmos de **_busca binária_**.

- O(n): Tempo de execução linear: O tempo de execução cresce proporcionalmente ao tamanho da entrada. Algoritmos lineares percorrem cada elemento da entrada uma vez. Exemplos incluem busca linear e algumas formas de ordenação.

- O(n * log n): Exemplo: um algoritmo rápido de ordenação, como a ordenação _**quicksort**_.

- O(n^2): Tempo de execução quadrático: O tempo de execução é o quadrado do tamanho da entrada. Algoritmos com essa complexidade são menos eficientes e podem levar muito tempo para processar grandes conjuntos de dados. Exemplos comuns são algoritmos de ordenação como o **_Bubble Sort_** e o **_Insertion Sort_**.

- O(n!): Exemplo: um algoritmo bastante lento, como o do **_caixeiro-viajante_**.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8t5jvifcgn1ts4r9fp6t.png)

Esses são apenas alguns exemplos das muitas possibilidades da notação Big O. Existem notações mais complexas, como **_O(n log n)_** e **_O(2^n)_**, que descrevem algoritmos com diferentes níveis de eficiência. É importante lembrar que a notação Big O descreve o pior caso possível de um algoritmo e nos dá uma visão geral de sua eficiência relativa.

Ao analisar algoritmos e escolher a melhor abordagem para um problema, é fundamental considerar a complexidade temporal e espacial. Um algoritmo com complexidade **_O(n)_** pode ser mais eficiente do que um algoritmo com complexidade **_O(log n)_**, dependendo do contexto e dos requisitos do problema.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/by7yfrzqcno7iiyq9eja.png)

**Algoritmos e suas respectivas notações Big O:**

1 - **Busca linear**: Este algoritmo percorre todos os elementos de uma lista até encontrar o elemento desejado ou chegar ao final da lista.

- Tempo de execução: O(n)

- Descrição: O tempo de execução aumenta linearmente com o tamanho da entrada, pois cada elemento precisa ser verificado.

2 - **Busca binária**: Este algoritmo é aplicável apenas a listas ordenadas. Ele divide repetidamente a lista ao meio e verifica se o elemento desejado está na metade esquerda ou direita.

- Tempo de execução: O(log n)

- Descrição: O tempo de execução cresce logaritmicamente com o tamanho da entrada, pois a lista é dividida pela metade a cada iteração.

3 - **Ordenação por Bubble Sort**: Neste algoritmo de ordenação, os elementos são comparados em pares e trocados se estiverem fora de ordem. O processo se repete até que a lista esteja ordenada.

- Tempo de execução: O(n^2)

- Descrição: O tempo de execução é quadrático em relação ao tamanho da entrada, pois são necessárias iterações múltiplas e cada elemento pode precisar ser comparado com todos os outros.

4 - **Ordenação por Merge Sort**: Este é um algoritmo de ordenação baseado em dividir para conquistar. A lista é dividida em sublistas menores, ordenadas separadamente e, em seguida, mescladas para obter a lista final ordenada.

- Tempo de execução: O(n log n)

- Descrição: O tempo de execução cresce em uma taxa logarítmica com o tamanho da entrada para dividir as sublistas e, em seguida, linearmente com o tamanho da entrada para mesclá-las.

5 - **Cálculo da soma de uma lista de números**: Este algoritmo simples percorre uma lista de números e calcula a soma total.

- Tempo de execução: O(n)

- Descrição: O tempo de execução é linear em relação ao tamanho da entrada, pois cada elemento da lista precisa ser visitado uma vez.

6 - **Busca em uma tabela de dispersão (hash table)**: Ao procurar um elemento em uma tabela de dispersão, a função **hash** é aplicada para determinar sua posição na tabela.

- Tempo de execução médio (em caso ideal): O(1)

- Descrição: O tempo de execução é constante, independentemente do tamanho da entrada, desde que não ocorram muitas colisões.

**Problema do caixeiro viajante**

O problema do caixeiro viajante é um desafio clássico de otimização combinatória, em que o objetivo é encontrar o menor caminho possível que passe por todas as cidades (ou pontos) visitando cada uma delas exatamente uma vez e retornando à cidade de origem.

A complexidade do problema do caixeiro viajante depende da abordagem utilizada para resolver o problema. Existem diferentes algoritmos para isso, e vou apresentar dois exemplos com suas respectivas notações Big O:

1 - **Força bruta (Brute Force)**:

- Tempo de execução: O(n!)

- Descrição: O tempo de execução cresce fatorialmente com o número de cidades. Esse algoritmo testa todas as permutações possíveis das cidades para encontrar o caminho mais curto.

2 - **Algoritmo heurístico (Algoritmo do vizinho mais próximo)**:

- Tempo de execução: O(n^2)

- Descrição: Neste algoritmo, cada cidade é visitada a partir da cidade atual escolhendo a cidade vizinha mais próxima que ainda não foi visitada. O tempo de execução é quadrático em relação ao número de cidades, pois em cada iteração é necessário encontrar a cidade mais próxima.

**A Big O estabelece o pior caso para o tempo de execução**

Vamos imaginar que você queira encontrar um nome em um lista ordenada e para isso vamos usar uma busca simples para percorrer. Um busca simples tem uma complexidade de **_O(n)_** vezes para ser executada, isso quer dizer que, no pior caso, terá que examinar cada registro até um determinado nome. Vamos supor que temos que buscar o nome **_Adriano_** se ele for o primeiro da lista então levará **_O(1)_** agora se o nome for o **_Zairro _**sendo o ultimo da lista temos **_O(n)_** sendo o pior caso.

Neste caso, **_O(1)_** é o melhor cenário, teve a sorte de achar Adriano no começo da lista. Mas a notação Big O leva em conta o pior dos casos, que é **_O(n)_** então a complexidade do algoritmo de busca simples é de **_O(n)_**. É uma reafirmação de que a busca simples nunca será mais lenta que **_O(n)_**.     

**Conclusão**

Em resumo, a notação Big O é uma ferramenta poderosa para medir a eficiência dos algoritmos, permitindo-nos comparar e selecionar a melhor solução para um determinado problema. Compreender e utilizar corretamente a notação Big O é essencial para os desenvolvedores de software, pois nos ajuda a escrever algoritmos eficientes e otimizados.

Espero que esta postagem tenha sido útil para vocês! Se tiverem mais dúvidas sobre a notação Big O ou qualquer outro tópico relacionado à ciência da computação, fiquem à vontade para perguntar.

Fontes:

[Grande-O - wikipedia](https://pt.wikipedia.org/wiki/Grande-O)
[Notação Big-O](https://pt.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation)
[Quantum Computing in Complexity Theory and Theory of Computation](http://www.austinmohr.com/Work_files/complexity.pdf)
[Know Thy Complexities!](https://www.bigocheatsheet.com/)
[Definição da notação "Big O"](https://pt.stackoverflow.com/questions/56836/defini%C3%A7%C3%A3o-da-nota%C3%A7%C3%A3o-big-o)
[Pesquisa binária](https://pt.wikipedia.org/wiki/Pesquisa_bin%C3%A1ria)
[A Busca Binária](https://www.blogcyberini.com/2017/09/busca-binaria.html)
[Busca Linear](https://www.blogcyberini.com/2017/09/busca-linear.html)
[Problema do Caixeiro Viajante](https://docs.ufpr.br/~volmir/PO_II_12_TSP.pdf)
[Problema do caixeiro-viajante - wikipedia](https://pt.wikipedia.org/wiki/Problema_do_caixeiro-viajante)