Notação Big O

11.1 Definição da notação Big O

A notação Big O é uma notação matemática usada para descrever o limite superior do tempo de execução ou do consumo de recursos de um algoritmo, dependendo do tamanho dos dados de entrada. Ela ajuda a determinar como o algoritmo se escala bem e como seu desempenho muda à medida que o volume de dados aumenta.

A notação Big O foca nos aspectos mais significativos do algoritmo, ignorando constantes e termos menos significativos, permitindo concentrar-se no comportamento de longo prazo do algoritmo.

Notações principais:

O(1) — Complexidade constante:

• O tempo de execução do algoritmo não depende do tamanho dos dados de entrada.
• Exemplo: acesso a um elemento de um array por índice.

O(n) — Complexidade linear:

• O tempo de execução do algoritmo depende linearmente do tamanho dos dados de entrada.
• Exemplo: iteração simples por todos os elementos de um array.

O(log n) — Complexidade logarítmica:

• O tempo de execução do algoritmo cresce logaritmicamente com o aumento do tamanho dos dados de entrada.
• Exemplo: busca binária em um array ordenado.

O(n^2) — Complexidade quadrática:

• O tempo de execução do algoritmo depende quadraticamente do tamanho dos dados de entrada.
• Exemplo: ordenação por bolha, ordenação por inserção.

O(2^n) — Complexidade exponencial:

• O tempo de execução do algoritmo depende exponencialmente do tamanho dos dados de entrada.
• Exemplo: solução do problema da mochila por força bruta.

Nota. Você aprenderá mais sobre busca binária, ordenação por bolha e o "problema da mochila" nas próximas aulas.

11.2 Interpretação da notação Big O

Como interpretar e usar a notação Big O?

Ignorando constantes e termos menos significativos: Big O descreve o crescimento da função, ignorando constantes e termos menos significativos. Por exemplo, O(2n) e O(3n) são interpretados como O(n).

Comparação de algoritmos: Big O permite comparar algoritmos por sua eficiência assintótica. Por exemplo, um algoritmo com O(n log n) é mais eficiente que um com O(n^2) para volumes de dados muito grandes.

Análise do pior caso: Big O é geralmente usado para analisar o pior caso do tempo de execução de um algoritmo, permitindo estimar sua complexidade máxima.

Ignorando constantes

Vamos ver exemplos de ignorar constantes e termos menos significativos:

Exemplo 1. Considere duas funções:

• f(n) = 3n + 2
• g(n) = 5n + 1

Ambas as funções têm complexidade linear, pois o termo dominante em cada função é n. Portanto, ambas as funções são interpretadas como O(n), apesar das diferenças nos coeficientes e termos adicionais.

Exemplo 2. Considere duas funções:

• f(n) = n^2 + 3n + 4
• g(n) = 2n^2 + n

Ambas as funções têm complexidade quadrática, pois o termo dominante é n^2. Ambas as expressões são interpretadas como O(n^2), apesar das diferenças nos outros termos e coeficientes.

11.3. Comparação de algoritmos

1. Comparação de algoritmos em volumes de dados muito grandes

Exemplo 1:

• O algoritmo A tem complexidade temporal O(n^2).
• O algoritmo B tem complexidade temporal O(n log n).

Para valores pequenos de n, o algoritmo A pode ser mais rápido devido a constantes menores, mas para valores grandes de n, o algoritmo B será significativamente mais rápido, pois seu crescimento é logarítmico e não quadrático.

Exemplo 2:

• O algoritmo X tem complexidade temporal O(n).
• O algoritmo Y tem complexidade temporal O(1).

O algoritmo Y sempre será mais rápido, independentemente do tamanho de n, já que O(1) significa que o tempo de execução do algoritmo não depende do tamanho dos dados de entrada.

2. Análise do pior caso

Exemplo 1:

O algoritmo de ordenação por bolha tem complexidade temporal O(n^2) no pior caso, quando o array está ordenado em ordem inversa. Isso significa que para cada elemento no array será necessário comparar e, possivelmente, trocar com cada outro elemento.

Exemplo 2:

A busca binária tem complexidade temporal O(log n) no pior caso. Isso significa que mesmo no pior caso o número de passos necessários para encontrar um elemento dependerá logaritmicamente do tamanho do array, o que é muito eficiente.

3. Impacto no desempenho e escalabilidade

Exemplo 1:

Se tivermos dois algoritmos para processar dados, um com complexidade temporal O(n^2) e outro com O(n log n), e aumentarmos o tamanho dos dados de 1000 elementos para 10 000 elementos, a diferença no desempenho será significativamente perceptível.

• O algoritmo com O(n^2) executará aproximadamente 100 000 000 operações para 10 000 elementos.
• O algoritmo com O(n log n) executará cerca de 40 000 operações para 10 000 elementos.

Exemplo 2:

Considere um algoritmo que funciona em O(2^n). Se aumentarmos o tamanho dos dados de entrada de 10 para 20 elementos, o número de operações aumenta exponencialmente.

• Para n = 10: 2^10 = 1024 operações.
• Para n = 20: 2^20 = 1 048 576 operações.

Isso mostra como a complexidade exponencial rapidamente se torna impraticável para valores grandes de n.