A análise da complexidade de algoritmos é essencial para avaliar seu desempenho e eficiência, especialmente em cenários com grandes volumes de dados. Assinale a opção que representa a complexidade O (n log n) mais comummente observada em algoritmos de ordenação eficientes.
- A)Algoritmos de ordenação por bolha (Bubble Sort).
Bubble Sort tem complexidade O(n^2), então não representa o padrão eficiente O(n log n).
- B)Algoritmos de ordenação por seleção (Selection Sort).
Selection Sort também é O(n^2), com desempenho ruim para grandes volumes de dados.
- C)Algoritmos de ordenação rápida (QuickSort).
QuickSort é um exemplo clássico de algoritmo de ordenação com complexidade média O(n log n).
- D)Algoritmos de ordenação por inserção (Insertion Sort).
Insertion Sort, em geral, tem complexidade O(n^2), apesar de ser bom em listas pequenas ou quase ordenadas.
- E)Algoritmos de ordenação usando contagem (Counting Sort).
Counting Sort não é O(n log n); sua complexidade depende do intervalo dos valores e costuma ser linear em certas condições.
Gabarito: C
Quando você olha para complexidade de algoritmos, a ideia é simples: quanto o tempo de execução cresce quando a entrada cresce? Em ordenação, isso costuma separar os algoritmos “amiguinhos do pequeno volume” dos que aguentam melhor grandes conjuntos de dados. Os algoritmos O(n^2), como bolha, seleção e inserção, parecem inocentes, mas ficam lentos rapidamente quando n aumenta. Já a classe O(n log n) é a queridinha dos algoritmos de ordenação eficientes. Ela aparece com frequência em métodos que dividem o problema em partes menores e depois recombinam tudo. É o caso do QuickSort, que em média trabalha nessa ordem de crescimento, por isso é muito lembrado em provas quando a banca fala em eficiência. No QuickSort, o vetor é particionado em torno de um pivô, e cada parte é ordenada recursivamente. Esse padrão de “dividir para conquistar” costuma gerar desempenho muito bom na prática e, em média, complexidade O(n log n). Por isso o gabarito é a alternativa C. Vale lembrar: a complexidade pode variar conforme o caso. O QuickSort tem pior caso O(n^2), mas a questão perguntou a complexidade mais comumente observada em algoritmos de ordenação eficientes, então o foco é o comportamento médio e clássico do algoritmo.