Big-O

Na ciência da computação, a notação Big-O é uma forma de descrever o desempenho ou complexidade de um algoritmo. Ela fornece um limite superior para a taxa de crescimento da complexidade de tempo (ou espaço) de um algoritmo em função de o tamanho da entrada.

O 'O' em Big-O significa 'ordem de' e descreve o pior cenário. Quando dizemos que um algoritmo é O(f(n)), onde f(n) é uma função do tamanho de entrada n, estamos expressando o limite superior da taxa de crescimento do algoritmo

Aqui estão algumas notações Big-O comuns e seus significados:

1. O(1): Complexidade de tempo constante. O tempo de execução ou uso de espaço do algoritmo é constante, independentemente do tamanho da entrada. Acessar um elemento em uma matriz por índice, por exemplo, normalmente é O(1).
2. O(log n): Complexidade de tempo logarítmica. Comum em algoritmos que dividem o problema ao meio em cada etapa, como pesquisa binária. Algoritmos eficientes para árvores de pesquisa balanceadas também costumam ter complexidade O(log n).
3. O(n): Complexidade de tempo linear. O desempenho do algoritmo cresce linearmente com o tamanho da entrada. Os exemplos incluem a iteração através de uma matriz ou lista.
4. O(n log n): Complexidade de tempo linear. Comum em algoritmos de classificação eficientes, como classificação por mesclagem e classificação por heap.
5. O(n^2): Complexidade de tempo quadrática. O desempenho é proporcional ao quadrado do tamanho da entrada. Frequentemente visto em loops aninhados.
6. O(n^2): Complexidade de tempo quadrática. O desempenho é proporcional ao quadrado do tamanho da entrada. Frequentemente visto em loops aninhados.
7. O(n!): Complexidade de tempo fatorial. Representa algoritmos que resolvem um problema de tamanho n resolvendo n problemas menores, cada um de tamanho n−1, e assim por diante. Extremamente ineficiente e deve ser evitado para entradas grandes.

A imagem abaixo mostra uma comparação gráfica do tempo entre os diferentes valores de O.

A imagem abaixo mostra uma comparação no código do tempo entre os diferentes valores de O.