Questão para a Prova Oral 051
Semana: 10/03/2003 a 14/03/2003
Assunto: HeapSort e QuickSort
Enunciado
Dados dois vetores A e B com m e n inteiros, respectivamente. Pergunta-se quais os tempos de execução para:
- ordenar A por meio do heapsort, caso A já esteja ordenado em ordem decrescente;
- ordenar B por meio do quicksort, caso B já esteja ordenado;
- juntar A e B de forma que o vetor resultante também fique ordenado;
|
A)
|
O(m);
|
O(1);
|
O( (m+n)*lg(m+n) )
|
|
|
B)
|
O(m*lg m);
|
O(n*lg n);
|
O( m*lg m) se m > n, caso contrário, O(n*lg n)
|
|
|
C)
|
O(m*lg m);
|
O(1);
|
O(m+n)
|
|
|
D)
|
O(m);
|
O(n*lg n);
|
O( (n+m)^2 )
|
|
|
|
Autor: Ricardo Luís Lachi
RA: 972929