[Prévia cron] [Próxima Cron] [Prévia por assunto] [Próxima por assunto]
[Índice cronológico] [Índice de assunto] [Índice de autor]

Re: exercicios


 1. Mostre que existem 2^n permutações do intervalo [1..n] que fazem o
    QuickSort visto em aula apresentar a sua pior performance. Faça um
    programa que lista estas permutações.

De fato, acho que o número correto deveria ser 2^{n-1} em vez de
2^n. Mas {3^(n-2)}*2 me parece muito grande. Produzam as 6 permutações
de 3 elementos que são candidatas ao pior desempenho e executem o QS
neles, calculando a somatória dos tamanhos dos trechos que são
particionados.

Imre Simon

: Date: Sat, 28 Oct 2000 22:57:02 -0200
: From: "Marcelo Amaral Rezende" <trezende@ime.usp.br>
: To: <is-5711-00@ime.usp.br>
: Subject: exercicios 
: 
: Eu e o Daniel Vieira  descutimos o primeiro exercicio da lista e chegamos a conclusao 
: que existe {3^(n-2)}*2 permutacoes de n-distintos inteiros e nao 2^n como sugerido
: 
: Marcelo