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

Re: exercicio 1

Marcelo,

eu verifiquei o exercício e acho que Você tem razão. No caso do
partition do livro, se o fiel for o menor ou o segundo menor elemento
então o primeiro bloco será unitário e caso o fiel seja o maior
elemento, o segundo bloco é que será unitário. Em qualquer outro caso
nenhum dos dois blocos será unitário. Aliás, esta constatação
faz parte da análise do algoritmo que está na página 164.

Isto torna a segunda parte do exercício, aquela de listar as
permutaçÕes que levam ao pior tempo de ordenação, mais interessante
ainda.

Obrigado pela observação.

Imre Simon

: Date: Sun, 29 Oct 2000 18:41:19 -0200
: From: "Marcelo Amaral Rezende" <trezende@ime.usp.br>
: To: <is-5711-00@ime.usp.br>
: Subject: exercicio 1 
: 
: Simon
: 
: Parece que estamos lidando com dois problemas distintos :
: 2*3^(n-2) é o numero de permutacoes de n-inteiros distintos  onde teremos o
: pior resultado na execucao do QS ,isto é o partition dividira
: (recursivamente) esta permutacao com um dos dois intervalo de comprimento
: sempre = 1
: Se for outro o problema que se esta estudando favor me esclarecer.
: Marcelo
: