Complexidade de algoritmos – O(log n), O(n), O(n log n), O(n²) e uma corrida de ordenação
ComputaçãoAlgoritmos e resolução de problemasIdades 15–16
Use com a sua turma: os alunos abrem por um link ou QR code, sem precisar de conta.
Continue em Algoritmos e resolução de problemas
Um gráfico mostra o número de passos em função do tamanho da entrada n para as funções log₂n, n, n·log₂n e n², junto com o número de comparações medido ao vivo para a ordenação por bolha (bubble sort) e o quicksort. Os alunos arrastam o marcador de n no gráfico para ler os valores e depois clicam em Corrida para ver os dois algoritmos ordenarem o mesmo vetor no mesmo ritmo de passos: o quicksort (n log n) termina antes da bolha (n²), e a diferença aumenta conforme n cresce.
Aula: Avaliação de algoritmos: número de operações em função do tamanho da entrada, notação O grande, comparação entre bubble sort e quicksort
O que mostra
A complexidade de um algoritmo descreve como o número de operações cresce quando o tamanho dos dados n aumenta, sem levar em conta fatores constantes. O gráfico compara quatro ritmos de crescimento: log₂n quase não sobe, n cresce na mesma proporção, n·log₂n cresce um pouco mais rápido e n² quadruplica toda vez que n dobra. As medições confirmam a teoria: num vetor aleatório, a bolha faz cerca de n²/2 comparações e o quicksort cerca de 1,4·n·log₂n. Com n pequeno a diferença quase não importa; com muitos dados, a escolha do algoritmo decide se um programa leva segundos ou horas.
Como usar
Comece com Curvas teóricas exibidas nas quatro funções e arraste sobre o gráfico para mudar n, lendo o valor de cada curva. Quando as curvas ficarem distantes demais para comparar, ative Escala log no eixo dos passos. Depois clique em Corrida para que os dois algoritmos ordenem o mesmo vetor no mesmo ritmo de passos, e repita com Novo vetor e um n maior para ver a diferença aumentar.
Parâmetros que você pode mudar
- Tamanho dos dados n 4–100
- Curvas teóricas exibidas log₂n, n, n·log₂n, n², n e n², log₂n, n e n·log₂n
- Escala log no eixo dos passos
- Velocidade da corrida 5–200 passos/s
Perguntas para explorar
- Quando n dobra de 50 para 100, por quanto n² é multiplicado, e aproximadamente por quanto n·log₂n é multiplicado?
- Por que a curva log₂n fica quase plana enquanto a curva n² sobe rapidamente?
- Com n = 10, quantas comparações a mais a bolha faz em relação ao quicksort, e essa diferença importa na prática?
