No Relatório Técnico de Zanetti e Meidanis - Construção incremental de árvores PQR (2010) encontramos várias menções a uma estrutura de dados que utiliza o algoritmo de union-find. Sobre esse algoritmo e seu uso na construção de árvores PQR, considere as afirmações:
- A estrutura é utilizada para encontrar rapidamente os filhos de um nó.
- O número de elementos que devem ser mantidos na estrutura de union-find é linear com o tamanho da entrada do algoritmo PQR.
- Nas implementações atuais do algoritmo de union-find, a operação find tem um custo computacional amortizado de O(a(n)), onde a(n) é o inverso da função de Ackermann.
- Durante a execução do algoritmo PQR, alguns elementos precisam ser removidos da estrutura union-find. E como o custo dessa operação é alto, o algoritmo PQR é dito quase-linear.
Estão corretas as afirmações:
- Apenas I e II.
- Apenas I , II e IV
- Apenas II e IV
- Apenas II e III
- NDA
Nenhum comentário:
Postar um comentário