Durante a aula de hoje discutimos o desempenho de melhor caso do Heapsort. O Tales e outros alunos (cujos nomes infelizmente não guardei) encontraram o seguinte artigo relacionado ao assunto:
Bollobás, Fenner, Frize,
"On the Best Case of Heapsort",
Journal of Algorithms 20, pp.205-217,
ano 1996.
O artigo é muito interessante e mostra que o vetor constante (todos os elementos iguais) é, essencialmente, a única família de instâncias em que o desempenho do Heapsort é O(n). Conforme o artigo, se nos restringirmos a vetores cujos elementos são dois a dois distintos, o Heapsort consome tempo Omega(n lg n).
(A propósito, o primeiro autor é "da pesada". Ele já esteve algumas vezes aqui na USP e foi o orientador do professor Yoshiharu. O terceiro autor também é "da pesada"; esteve aqui num workshop em 2005. Não conheço o segundo autor, mas provavelmente ele também é bamba.)
Professor, depois da aula e após ler sobre o quicksort no The design and analysis of computer algorithms, do Aho, Hopcroft e Ullman, lembrei de uma informação que alguem me falou ha algum tempo (não lembro, mas acho que foi meu professor na graduação). O limite inferior de algoritmos baseados em comparação (e que usam uma arvore de decisão) não é Omega(n lg n)? Não seria esse o caso do heapsort?
Acho que o simples fato de existir um caso que é n já prova que tal teoria não é válida, ainda que seja apenas um caso. Você deve estar confundindo com o limite inferior do pior caso, ou seja, não dá para fazer um algoritmo melhor do que O(n lg n). Mas deixo para o professor confirmar a informação...
É isso mesmo. A cota inferior vale para o pior caso (e não para o melhor caso).
Realmente, acho até que foram com palavras parecidas com as suas. Foi realmente confusão minha. Obrigado.
Pra quem quiser, o link do artigo é este:
http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WH3-45MH2FH-1H&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=dd6c933d26bdfb06b749f52633a58a17
Para pegar, tem que estar na rede da USP.
http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WH3-45MH2FH-1H&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=dd6c933d26bdfb06b749f52633a58a17
Para pegar, tem que estar na rede da USP.