Notação Big O: conceitos básicos

2.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 consumo de recursos de um algoritmo, dependendo do tamanho dos dados de entrada. Ela ajuda a definir como bem um algoritmo escala e como seu desempenho muda ao aumentar o volume de dados.

A notação Big O foca nos aspectos mais significativos do algoritmo, ignorando constantes e termos menos significativos, permitindo que nos concentremos no comportamento a 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 de 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.

2.2 Interpretação da notação Big O.

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

Ignorar constantes e termos menos significativos:

Big O descreve a taxa de crescimento de uma 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 a comparação de algoritmos pela sua eficiência assintótica. Por exemplo, um algoritmo com O(n log n) é mais eficiente do que um algoritmo com O(n^2) para volumes de dados muito grandes.

Análise do pior caso:

Big O é geralmente usado para análise do pior caso do tempo de execução de um algoritmo, o que permite estimar sua complexidade máxima.

Ignorar constantes.

Ignore 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, já que o termo dominante em cada função é n. Portanto, ambas 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.

2.3. Comparação de algoritmos

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

Exemplo 1:

• O algoritmo A tem uma complexidade de tempo O(n^2).
• O algoritmo B tem uma complexidade de tempo O(n log n).

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

Exemplo 2:

• O algoritmo X tem uma complexidade de tempo O(n).
• O algoritmo Y tem uma complexidade de tempo O(1).

O algoritmo Y será sempre 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 uma complexidade de tempo 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 todos os outros elementos.

Exemplo 2:

A busca binária tem uma complexidade de tempo 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 temos dois algoritmos para processar dados, um com complexidade de tempo O(n^2), e outro com O(n log n), e aumentamos o tamanho dos dados de 1000 elementos para 10.000 elementos, a diferença no desempenho será bastante 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 opera em O(2^n). Se aumentarmos o tamanho dos dados de entrada de 10 para 20 elementos, o número de operações cresce exponencialmente.

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

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