Considere o algoritmo a seguir (bastante deselegante) para imprimir três números em ordem crescente.

Algoritmo 5.18 Imprimindo três números em ordem por força bruta.

Condições prévias:
Condições posteriores:Os elementos de são impressos em ordem crescente.
se \(a<b\) então
    「 se \(b<c\) então
            imprimir \(a, b, c\)
        senão
            「 se \(a<c\) então
                    imprimir \(a, c, b\)
                senão
    \(\llcorner\quad\llcorner\quad\) imprimir \(c, a, b\)
senão
    「 se \(a<c\) então
            imprimir \(b, a, c\)
    senão
            「 se \(b<c\) então
                    imprimir \(b, c, a\)
                senão
                imprimir \(c, b, a\)
(a)Desenhe uma árvore de decisão para modelar as escolhas feitas por esse algoritmo.
(b)Esse algoritmo é ótimo com respeito ao número de comparações<?Explique.

Passo 1

O enunciado apresenta um algoritmo que, por força-bruta, compara a,b,cinR para imprimir esses três valores em ordem crescente.
Conteúdo: construção de árvore de decisão e análise de comparações em algoritmo de ordenação.

Passo 2

A árvore de decisão (cada nó é um teste, cada ramo “sim” ou “não”) é:
c (a < b?) / backslash sim não / backslash (b < c?) (a < c?) / backslash / backslash sim não sim não | | | | imprimir a,b,c (a < c?) imprimir b,a,c (b < c?) / backslash / backslash sim não sim não | | | | imprimir a,c,b imprimir c,a,b imprimir b,c,a imprimir c,b,a ããããã

Passo 3

1. Cada caminho da raiz a uma folha faz no máximo três testes (comparações).
2. Para ordenar três elementos precisamos distinguir 3!=6 permutações, logo o limite inferior de comparações no pior caso é
lceil log2(6)rceil = 3
3. Como o algoritmo usa exatamente <=3 comparações em todo caso, atinge esse limite mínimo.

Resposta

(a) Veja a árvore de decisão descrita no Passo 2.
(b) Sim. O algoritmo faz no máximo ,3 comparações e o limite inferior para ordenar três elementos é lceillog2(3!)rceil=3, logo ele é ótimo nesse sentido.

Exercícios de Livros Relacionados