O que é Big O?
"Big O" é uma notação usada para medir o custo de um algoritmo em termos de tempo de execução ou uso de recursos como o espaço de memória, também conhecidos como complexidade.
Como funciona?
Em termos simples, a notação descreve como o tempo de execução (ou espaço de memória) cresce à medida que os dados de entrada (representados pela letra n) aumentam.
Principais classes de complexidade
Complexidade constante
-
Representação:
O(1)
- O custo do algoritmo independe do tamanho de n. As instruções são executadas um número fixo de vezes.
// Independentemente do tamanho do vetor,
// a instrução é executada uma única vez
public static int exemplo1(int[] vetor) {
return vetor[vetor.length / 2];
}
Complexidade linear
-
Representação:
O(n)
- O custo do algoritmo cresce linearmente com o tamanho de n. Cada elemento de entrada precisa ser processado uma vez.
// Este algoritmo percorre cada elemento do vetor uma vez, somando os valores
public static int exemplo2(int[] vetor) {
int soma = 0;
for (int i = 0; i < vetor.length; i++) {
soma += vetor[i];
}
return soma;
}
Complexidade quadrática
-
Representação:
O(n²)
- O custo do algoritmo aumenta quadraticamente com o tamanho de n. Normalmente ocorre quando há dois loops aninhados.
// Este algoritmo implementa um método de ordenação, o Bubble Sort
public static void bubbleSort(int[] vetor) {
int temp;
for (int i = 0; i < vetor.length - 1; i++) {
for (int j = 0; j < vetor.length - i - 1; j++) {
if (vetor[j] > vetor[j + 1]) {
temp = vetor[j];
vetor[j] = vetor[j + 1];
vetor[j + 1] = temp;
}
}
}
}
Complexidade logarítmica
-
Representação:
O(log n)
- O custo do algoritmo cresce de forma logarítmica com o tamanho de n. É comum em algoritmos de busca ou de divisão e conquista.
// Este algoritmo realiza uma busca binária em um vetor ORDENADO
public static int exemplo4(int[] vetor, int chave) {
int esquerda = 0;
int direita = vetor.length - 1;
while (esquerda <= direita) {
int meio = esquerda + (direita - esquerda) / 2;
if (vetor[meio] == chave) {
return meio;
}
if (vetor[meio] < chave) {
esquerda = meio + 1;
} else {
direita = meio - 1;
}
}
return -1;
}
Complexidade e otimização
O gráfico à seguir demonstra, em termos de eficiência de tempo e memória, quais complexidades apresentam melhor desempenho quando os parâmetros de entrada tendem ao infinito:
Gráfico: https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/
Top comments (0)