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

Usar com minha turma

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. Uma segunda tela, Caixeiro-viajante, coloca cidades num mapa e compara a força bruta, que verifica todas as (n − 1)!/2 rotas e logo precisa de um tempo não razoável, com a rápida heurística do vizinho mais próximo.

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 log₂n, n, n·log₂n e n²; as medições mostram a bolha perto de n²/2 comparações e o quicksort perto de 1,4·n·log₂n. Alguns problemas são muito piores. A tela do caixeiro-viajante testa todas as rotas, que são (n − 1)!/2: cada cidade a mais multiplica o trabalho e 16 cidades levariam horas. Uma heurística como o vizinho mais próximo responde em n(n − 1)/2 passos, rápido, mas nem sempre com a rota mais curta.

Como usar

Arraste no gráfico para mudar n e ative Escala log quando as curvas ficarem muito distantes; clique em Corrida para ver as ordenações. Depois clique em Caixeiro: toque no mapa para adicionar cidades, clique em Força bruta e Vizinho mais próximo, e compare as rotas e os passos. Mude Número de cidades e Velocidade do computador para ver o tempo explodir.

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, n, n², 2ⁿ e n!
  • Escala log no eixo dos passos
  • Velocidade da corrida 5–200 passos/s
  • Tela Gráfico de complexidade, Caixeiro-viajante
  • Número de cidades (caixeiro-viajante) 4–16
  • Semente aleatória das cidades 1–999
  • Velocidade do computador 10⁶ passos por segundo, 10⁹ passos por segundo, 10¹² passos por segundo

Perguntas para explorar

  1. Quando n dobra de 50 para 100, por quanto n² é multiplicado, e aproximadamente por quanto n·log₂n é multiplicado?
  2. Por que a curva log₂n fica quase plana enquanto a curva n² sobe rapidamente?
  3. Com n = 10, quantas comparações a mais a bolha faz em relação ao quicksort, e essa diferença importa na prática?