Questão para a Prova Oral 140
Semana 10: 7 e 09/05/03
Assunto: Conjuntos Disjuntos e Algoritmos em Grafos
Quanto às operações em conjuntos
disjuntos, considerando m operações feitas sobre um universo de
n elementos, pode-se afirmar que:
A) A heurística de união por posto acarreta, por si só,
um tempo de execução de O(n lg m)
B) A combinação da heurística de união por
posto com a heurística de compressão de caminho acarreta um
tempo de execução de O(m lg* n)
C) A heurística de compressão de caminho acarreta, por si
só, um tempo de execução de O(m \alpha(m,n))
D) A combinação da heurística de união por
posto com a heurística de compressão de caminho acarreta um
tempo de execução de O(n \alpha(m,n))
E) N.D.A.
Autor: Augusto Jun Devegili
RA: 25620