Disciplinas UFC

Construção e Análise de Algoritmos

aula 09:  O problema da mediana   (pdf, video)

< Figura >
plano da aula  

1.  Introdução   
  1. Encontrando a mediana em tempo O(n log n)

2.  O algoritmo de divisão e conquista   
  1. tempo O(  n 1.58 )

3.  O algoritmo QuickMediana   
  1. tempo médio O(n)

4.  Mediana em tempo linear   
  1. tempo O(n), no pior caso
lista de exercícios 09   (pdf)
exercício 1:   A terciana
< Figura >
exercício 2:   Porque 5?
< Figura >
exercício 3:   Mediana em listas ordenadas
< Figura >
exercício 4:   Seleção múltipla
< Figura >


↩︎ Voltar