Construcao e Analise de Algoritmos - Teste 11 --------------------------------------------- Analise do algoritmo Heap-Sort A informacao sobre a ordem relativa dos elementos de um conjunto X pode ser representada na forma de um conjunto de pares ordenados P, que correspondem 'a relacao "<". Ou seja, se esta em P, entao aj < ak. Um conjunto de pares ordenados P e' dito uma ordem parcial se 1) esta em P ==> nao esta em P 2) e estao em P ==> esta em P Uma ordem total e' simplesmente uma ordem parcial com tamanho maximo, e portanto corresponde a uma ordenacao completa de X. E' facil ver que, se P e' uma ordem total, entao |P| = n(n-1)/2. Desta forma, podemos dizer que o objetivo de um algoritmo de ordenacao e' construir uma ordem total para os elemento de uma lista A = {a1, a2, ..., an}. Se o algoritmo de ordenacao e' baseado em comparacoes, entao ele constroi a ordem total a partir de perguntas do tipo: "aj < ak ?". Caso positivo, o par e' colocado em P, juntamente com todos os outros pares que podem ser obtidos por transitividade. Ou seja, o algoritmo inicia com o conjunto P vazio e, a cada passo, acrescenta novos pares ordenados a P, ate' que |P| = n(n-1)/2. Podemos estudar a eficiencia de um algoritmo de ordenacao imaginando a sua execucao como um jogo entre o algoritmo e um possivel adversario. Uma rodada do jogo se inicia com o algoritmo escolhendo um par de elementos aj e ak para fazer a comparacao. Podemos supor que nenhum algoritmo razoavel seleciona ak e aj se o par ou o par ja' se encontra em P. Assim, no instante da comparacao, o algoritmo nao possui nenhuma informacao sobre a ordem relativa de aj e ak, e e' o adversario quem decide se o resultado da comparacao e' verdadeiro ou falso. O objetivo do adversario e' escolher os resultados das comparacoes de modo que o tempo de execucao do algoritmo seja o maior possivel. Exemplo: A = {a1,a2,a3,a4} algoritmo | adversario | P ----------------------------------------------------------------------------- a1 < a2 ? | SIM | {} a3 < a4 ? | SIM | {;} a2 < a3 ? | NAO | {;;} a2 < a4 ? | NAO | {;;;} a1 < a3 ? | SIM | {;;;;;} ---------------------------------------------------------------------------- a) Mostre que no exemplo acima o adversario nao joga da melhor maneira possivel. Ou seja, se o adversario respondesse uma (ou mais) perguntas do algoritmo de maneira diferente, entao o algoritmo seria forcado a realizar uma pergunta a mais para completar a ordem total P. b) Por outro lado, mostre que se o algoritmo escolhesse suas perguntas de maneira mais cuidadosa, ele poderia completar a ordem total P com apenas 4 perguntas (independentemente das respostas do adversario). c) Suponha para este item que, apos a primeira pergunta, e enquanto for possivel, o algoritmo seleciona a cada passo um elemento que ja' foi comparado e um elemento novo para a proxima comparacao. Mostre que, se este for o caso, entao existe uma estrategia para o adversario tal que, apos n-1 comparacoes o conjunto P possui apenas n-1 pares ordenados. (Ou seja, em nenhum momento o algoritmo inclui um par em P por transitividade.) Dica: Analise a situacao utilizando um grafo direcionado. d) Proponha uma estrategia mais eficiente para as primeiras n-1 comparacoes do algoritmo. e) Estime o tamanho de P apos as n-1 comparacoes da sua estrategia. Algoritmo Heap-Sort ------------------- A ideia do algoritmo Heap-Sort consiste em utilizar suas comparacoes iniciais para construir uma estrutura de heap dentro do conjunto P Uma vez que esta estrutura esteja montada, a cada comparacao adicional o algoritmo pode incluir um grande numero de pares por transitividade no conjunto P (independentemente da resposta fornecida pelo adversario). Isto faz com que ele possa completar a ordem total de maneira eficiente. f) Apresente uma estrategia para o algoritmo que o permita construir a estrutura de heap dentro do conjunto P utilizando O(n) comparacoes. g) Argumente que, apos a montagem do heap, o algoritmo pode escolher comparacoes que o permitem adicionar Theta(log n) pares ordenados em P por transitividade, a cada passo. h) Utilize o resultado do item (g) para provar que o algoritmo Heap-Sort executa em tempo O(n log n).