MO417 - Questão para a prova oral

Número: 026

Enunciado:

Na prova do limite inferior para ordenações por comparação estudada em sala são usadas árvores binárias cheias para mostrar que todo algoritmo de ordenação por comparação vai usar Omega(n lg n) comparações. As árvores usadas tem as seguintes características:

1. Para cada algoritmo existe uma árvore, que é a mesma para todos os tamanhos de entrada, e todos os caminhos da raiz até as folhas são diferentes execuções do algoritmo.
2. Para cada entrada de tamanho n existe uma árvore, que é compartilhada por todos os algoritmos, e cada algoritmo diferente faz um caminho diferente nela.
3. Para cada tamanho n e cada algoritmo existe uma árvore, e todos os caminhos da raiz até as folhas são diferentes execuções do algoritmo.
4. Para qualquer tamanho de entrada e para qualquer algoritmo existe só uma árvore, e o caminho feito nessa árvore vai depender do algoritmo e do tamanho da entrada.
5. NDA

Autor(a): Alexandre Tachard Passos