MO417 - Questão para a prova oral
Número: 037
Enunciado:
O algoritmo de programação dinâmica para o problema da árvore
de busca binária ótima leva um tempo proporcional a n³ para ser
executado, enquanto o algoritmo para a construção da árvore do
código de huffman leva apenas um tempo proporgional a n lg n. Por
que isso é assim, se os dois problemas são tão parecidos?
- É assim pelo fato de que o código de huffman não tem que
lidar com a possibilidade de não encontrar um elemento na árvore;
é isso o que causa a complexidade do algoritmo de árvore de busca
binária ótima ser cúbico.
- É assim por acidente de projeto de algoritmo, já que uma
árvore do código de huffman é uma árvore de busca binária
ótima.
- É assim porque o código de huffman não diz nada sobre a ordem
dos elementos na árvore, e remover essa restrição simplifica
bastante o problema.
- É assim porque o código de huffman codifica caracteres, que
são bem menores que as palavras guardadas na árvore de busca
binária ótima, que podem ser arbitrariamente grandes.
- NDA
Autor(a): Alexandre Tachard Passos