MO417 - Questão para a prova oral
Número: 034
Enunciado:
Sobre a obtenção de árvores de busca binária ótimas, pode-se afirmar que:
- A solução memoizada tem tempo de execução da ordem Omega(2^n) enquanto a solução recursiva tem tempo de execução da ordem O(n^3)
- A solução apresenta duas matrizes resultantes: uma com a soma das probabilidades das chaves e a outra com as raízes das subárvores geradas
- A solução utiliza as probabilidades de ocorrência das chaves para determinar o custo esperado de uma busca em uma dada árvore/subárvore
- É um problema que não pode ser resolvido por programação dinâmica
- NDA
Autora: Juliana Galvani Greghi