Big O e Ordenação
Nota Conceitual:
Big O é a notação usada para descrever como o tempo de execução (ou uso de memória) de um algoritmo cresce em relação ao tamanho da entrada n. Trata-se de uma estimativa, não de um cálculo exato: constantes e termos de menor ordem são descartados, mantendo-se apenas o termo dominante. Por exemplo, O(2n² + 3n + 1) simplifica para O(n²). Na prática, analisamos sempre o pior caso, e a complexidade de tempo costuma ser estimada contando o número de laços for aninhados.
Algoritmos de ordenação são o campo clássico para aplicar Big O. Os algoritmos O(n²) - Bubble Sort, Selection Sort e Insertion Sort - são simples de implementar, mas não escalam. Os algoritmos O(n log n) - Merge Sort, Quicksort e Heapsort - são a escolha para entradas grandes. O Selection Sort executa aproximadamente n²/2 operações independentemente da ordem dos dados de entrada, mesmo um array já ordenado passa por todo o processo. Já o Merge Sort garante sempre O(n log n) no melhor e no pior caso, enquanto o Quicksort oscila entre O(n log n) em média e O(n²) no pior caso.
Além de tempo, avalie dois critérios extras ao escolher um algoritmo. Estabilidade: um sort estável preserva a ordem relativa de elementos iguais após a ordenação, propriedade essencial quando se ordena o mesmo conjunto por múltiplos critérios. In-place: algoritmos in-place operam diretamente no array original, usando apenas espaço constante O(1) extra, uma vantagem clara em datasets grandes. Bubble Sort e Insertion Sort são estáveis e in-place; Merge Sort é estável, mas usa O(n) de memória extra.