Notação Big O
A notação Big O é uma ferramenta matemática essencial para analisar o comportamento de algoritmos à medida que o tamanho da entrada cresce.
A notação Big O é uma ferramenta matemática essencial para analisar o comportamento de algoritmos à medida que o tamanho da entrada cresce, seja tendendo a um valor específico ou ao infinito.
Em outras palavras, a notação Big O expressa a complexidade de um algoritmo em termos de funções matemáticas. Ela fornece uma maneira de descrever a eficiência de um algoritmo em relação ao tamanho da entrada.
Níveis de Complexidade
Constante — O(1)
Algoritmos com complexidade constante são caracterizados por um número fixo de operações independentemente do tamanho da entrada N.
Isso significa que o tempo de execução não aumenta à medida que o tamanho da entrada cresce.
Linear — O(n)
Algoritmos com complexidade linear executam uma quantidade de operações que é diretamente proporcional ao tamanho dos dados de entrada. Isso significa que, à medida que o tamanho da entrada aumenta, o tempo de execução do algoritmo também aumenta na mesma proporção.
Logarítmica — O(log n)
Algoritmos com complexidade logarítmica são comuns em problemas que utilizam a estratégia de divisão e conquista, onde um problema grande é dividido em problemas menores e mais gerenciáveis. Um exemplo clássico desse tipo de algoritmo é a busca binária.
Algoritmos com complexidade logarítmica são eficientes para problemas onde a entrada pode ser dividida em subproblemas menores, e o número de operações necessárias cresce de forma muito mais lenta em comparação com a complexidade linear.
Linearítmica — O(n log n)
Algoritmos com complexidade linearítmica são comuns em problemas que combinam características de complexidade linear e logarítmica. Um exemplo clássico é o algoritmo de ordenação QuickSort.
No QuickSort, a lista de elementos é dividida em subgrupos e cada subgrupo é ordenado separadamente. Em seguida, as soluções parciais são combinadas para obter a solução final. O tempo de execução do QuickSort é O(n log n) pois o algoritmo divide a lista de elementos N vezes (complexidade linear) e, em cada divisão, o tamanho dos subgrupos é reduzido pela metade (complexidade logarítmica).
Quadrático — O(n²)
Algoritmos com complexidade quadrática são caracterizados pelo aumento do tempo de execução de forma quadrática com o tamanho da entrada N. Isso significa que o tempo necessário para a execução do algoritmo aumenta quadráticamente à medida que o tamanho dos dados de entrada aumenta.
Um exemplo comum de algoritmo com complexidade quadrática é o algoritmo de ordenação BubbleSort.
Exponencial — O(2ⁿ)
Algoritmos com complexidade exponencial são caracterizados pelo aumento exponencial do tempo de execução com o tamanho da entrada N. Isso significa que o tempo necessário para a execução do algoritmo cresce de forma exponencial à medida que o tamanho dos dados de entrada aumenta.
Fatorial — O(n!)
Esses algoritmos são extremamente ineficientes para conjuntos de dados moderadamente grandes, devido ao rápido crescimento do número de operações necessárias. Um exemplo comum de problema que resulta em complexidade fatorial é gerar todas as permutações de uma lista.