GabaritoE — Errado
Gabarito: ❌ ERRADO. A afirmação de que um algoritmo de complexidade n log n é mais complexo que um de complexidade n² está incorreta. Na análise assintótica de algoritmos, n² cresce muito mais rapidamente que n log n para grandes valores de n. Portanto, n log n é assintoticamente menos complexo (mais eficiente) do que n².
A notação Big O (O) descreve o limite superior do crescimento de uma função. As classes de complexidade mais comuns, ordenadas da mais eficiente para a menos eficiente, são:
Classe | Notação | Exemplo |
|---|---|---|
Constante | O(1) | Acesso a um elemento de array |
Logarítmica | O(log n) | Busca binária |
Linear | O(n) | Percorrer um array |
Linearítmica | O(n log n) | Merge sort, Quick sort (médio caso) |
Quadrática | O(n²) | Bubble sort, Insertion sort (pior caso) |
Exponencial | O(2ⁿ) | Recursão da Torre de Hanói |
A ordem de crescimento (do menor para o maior) é:
Comparando n log n e n²: para n = 10, n log n ≈ 10 × 3,32 ≈ 33,2 e n² = 100; para n = 100, n log n ≈ 100 × 6,64 ≈ 664 e n² = 10.000; para n = 1000, n log n ≈ 1000 × 9,97 ≈ 9970 e n² = 1.000.000. A diferença se acentua com o aumento de n, mostrando que n² é muito mais custoso.
Portanto, a assertiva está ERRADA: n log n é menos complexo (mais rápido) que n².
Na prova, lembre-se da hierarquia das classes de complexidade. A banca frequentemente inverte a ordem de grandezas para testar seu conhecimento. Memorize a sequência: constante < logarítmica < linear < linearítmica < quadrática < exponencial. 📈
Link permanente: /questoes/qq375809