Complexidade de Algoritmos - Big (O)
A notação Big O (O) é usada para descrever a complexidade de tempo de um algoritmo, expressando como o tempo de execução cresce à medida que o tamanho dos dados de entrada aumenta. Ela fornece uma forma padronizada de comparar e classificar a eficiência de diferentes algoritmos.
A notação Big O representa uma estimativa superior do tempo de execução, ou seja, descreve o pior caso possível em termos de desempenho. Ela se concentra nos fatores dominantes que influenciam o crescimento do tempo de execução, ignorando constantes e termos de menor ordem.
Por exemplo:
O(n)indica um tempo de execução linear, onde o tempo cresce proporcionalmente ao tamanho da entrada.O(n²)indica um tempo quadrático, onde o tempo de execução cresce com o quadrado do tamanho da entrada.
É importante notar que a notação Big O não fornece o tempo real de execução, mas sim uma estimativa teórica que ajuda a comparar algoritmos com base em seu comportamento assintótico.
Tipos de Complexidade de Tempo (Notação Big O)
De modo geral, algoritmos com complexidade de tempo menor (como O(1) ou O(log n)) são considerados mais eficientes do que aqueles com complexidade maior (como O(n) ou O(n²)), especialmente para grandes volumes de dados.
Tempo constante – O(1): O tempo de execução é independente do tamanho dos dados de entrada. Isso significa que, não importa se a entrada tem 10 ou 1.000.000 de elementos, o tempo necessário para executar a operação permanece o mesmo. Um exemplo clássico é o acesso direto a um elemento de um array.
Tempo linear – O(n): O tempo de execução cresce proporcionalmente ao tamanho da entrada. Ou seja, se o número de elementos na entrada dobra, o tempo de execução também dobra. Um exemplo típico é percorrer uma lista com um único loop.
Tempo logarítmico – O(log n): A cada iteração, o tamanho do problema é reduzido, geralmente pela metade. Isso torna o algoritmo extremamente eficiente mesmo com entradas grandes. Um bom exemplo é a busca binária em uma lista ordenada.
Tempo quadrático – O(n²): O tempo de execução cresce proporcional ao quadrado do tamanho da entrada. Esse tipo de complexidade é comum em algoritmos com loops aninhados, como o bubble sort ou o selection sort. Se a entrada dobra, o tempo de execução pode quadruplicar.
Tempo exponencial – O(2ⁿ): O tempo de execução dobra a cada novo elemento na entrada. Algoritmos com essa complexidade geralmente exploram todas as combinações possíveis, como ocorre em abordagens de força bruta para problemas de otimização, como o problema da mochila.
Tempo fatorial – O(n!): O tempo de execução cresce de forma extremamente rápida, seguindo o crescimento fatorial do tamanho da entrada. Esse tipo de complexidade é típico de algoritmos que geram todas as permutações possíveis de um conjunto, como no problema do caixeiro viajante. Na prática, torna-se inviável para entradas com n maior do que 15 ou 20.
| Complexidade | Nome | Escalabilidade | Exemplo típico |
|---|---|---|---|
| O(1) | Constante | 🔹 Excelente | Acesso direto a array |
| O(log n) | Logarítmica | 🔹 Muito boa | Busca binária |
| O(n) | Linear | ⚪ Moderada | Loop simples |
| O(n²) | Quadrática | 🔸 Ineficiente | Bubble sort, seleção |
| O(2ⁿ) | Exponencial | 🔴 Muito ruim | Problema da mochila |
| O(n!) | Fatorial | 🔴 Praticamente inviável | Permutações, TSP |
Para saber mais: