Número: 103
Enunciado:
Com relação ao primeiro algoritmo para a construção de árvores PQR, descrito em On the consecutives ones property por Meidanis et al, qual passo do algoritmo não pode ser executado em tempo linear?
- Encontrar um conjunto H não-trivial.
- Decompor o problema em dois sub-problemas.
- Juntar as árvores de cada sub-problema.
- Testar se uma coleção prima é trivial.
- NDA
a) Correta. No presente momento não sabemos se esse passo está em tempo linear.
ResponderExcluirb) Errada. Esse passo é em tempo linear, pois
é a soma do tamanho dos conjuntos.
c) Errada. Nesse passo, cada operação para juntar as árvores é constante, para cada nó o tempo total é linear.
d) Errada. Pois esse passo só verifica se possui restrições.
e) Errada.
Oi Diego,
ResponderExcluirBom comentário. Só queria que você mudasse o seguinte:
(a) não se diz "está" em tempo linear. Melhor dizer "pode ser executado" em tempo linear.
(b) novamente, é melhor trocar "é em tempo linear" por "pode ser executado em tempo linear". E a segunda frase deveria ser mais clara: "pois o esforço necessário é proporcional à soma dos tamanhos dos conuntos".
(c) Não entendi o que você quis dizer com "para cada nó o tempo total é linear". A operação pode ser executada em tempo constante ou não?