7.2-2
49 views
Skip to first unread message
Igor Medeiros
May 12, 2012, 7:32:54 PM5/12/12
to algoritmo...@googlegroups.com
7.2-2 Qual é o tempo de execução do quicksort quando todos os elementos do array A tem o mesmo valor?
Estou em dúvida porque acho que essa resposta depende do partition usado. Pra o primeiro partition proposto, seria O(n log n). Mas pro partition compacto da página 171 do cormen 3.ed seria O(n ²)
Vocês acham o mesmo?
Murilo Adriano Vasconcelos
May 12, 2012, 7:40:58 PM5/12/12
to algoritmo...@googlegroups.com
Considerando o partition do livro (pág 171 do CRLS em inglês) a complexidade é O(n^2) mesmo.
Você pode usar o resultado do exercício 7.1-2 para verificar que o partition para n elementos sempre vai retornar uma partição de tamanho n-1 e a outra de tamanho 0, o que faz a recorrência do quicksort ser T(n) = T(n - 1) + theta(n), o que você deve ter provado no exercício 7.2-1 ser O(n^2).
Igor Medeiros
May 12, 2012, 7:52:30 PM5/12/12
to algoritmo...@googlegroups.com
obrigado murilo
não sei se todos sabem, mas na quarta o prof. disse que é muito provável cair uma questão sobre o quicksort
Murilo Adriano Vasconcelos
May 12, 2012, 7:57:49 PM5/12/12
to algoritmo...@googlegroups.com
A prova é terça, 7h da matina!
Ricardo Correa
May 12, 2012, 8:43:00 PM5/12/12
to algoritmo...@googlegroups.com
Oi Igor,
ele comentou mais alguma coisa ?
A parte que mais me preocupa do quick-sort é aquela seção 7.4 que tem a analise do tempo e comparações do quick sort com a versão randômica do mesmo.
Se tiver mais informações ou comentários dele, avisa aí a gente.
Valeu,
Ricardo
ele comentou mais alguma coisa ?
A parte que mais me preocupa do quick-sort é aquela seção 7.4 que tem a analise do tempo e comparações do quick sort com a versão randômica do mesmo.
Se tiver mais informações ou comentários dele, avisa aí a gente.
Valeu,
Ricardo
2012/5/12 Murilo Adriano Vasconcelos <mur...@clever-lang.org>
Igor Medeiros
May 12, 2012, 8:48:37 PM5/12/12
to algoritmo...@googlegroups.com
ele falou que nao cai questões sobre tempo de execução esperado.
acho que as análises mais complicadas nao vão cair. acho que a prova será nos mesmos moldes da prova anterior. mas isso é só achismo mesmo
Ricardo Correa
May 12, 2012, 8:54:42 PM5/12/12
to algoritmo...@googlegroups.com
Bom, esta informação já me deixa um pouco mais animado, pq tem umas provas de tempo de execução bem complicadas.
Valeu,
Ricardo
Igor Medeiros
May 13, 2012, 2:41:12 PM5/13/12
to algoritmo...@googlegroups.com
Oi pessoal,
Obrigado
atilio gomes
May 13, 2012, 3:41:34 PM5/13/12
to algoritmo...@googlegroups.com
Igor, acho que para essa entrada ele não é estável:
8* 5 8 4 1
pois no final ela fica 1 4 5 8 8*
8* 5 8 4 1
pois no final ela fica 1 4 5 8 8*
Ricardo Correa
May 13, 2012, 3:55:57 PM5/13/12
to algoritmo...@googlegroups.com
boa.....
Parece que qq entrada que o primeiro numero seja o maior, o ultimo seja o menor e o maior numero se repita no meio, causa a instabilidade. Isto se assumirmos a implementação do Cormen que usa o pivô como sendo o ultimo numero.
Valeu,
Ricardo
Parece que qq entrada que o primeiro numero seja o maior, o ultimo seja o menor e o maior numero se repita no meio, causa a instabilidade. Isto se assumirmos a implementação do Cormen que usa o pivô como sendo o ultimo numero.
Valeu,
Ricardo
2012/5/13 atilio gomes <gomes....@gmail.com>
Igor Medeiros
May 13, 2012, 5:58:29 PM5/13/12
to algoritmo...@googlegroups.com
eu havia encontrado outra
3 1 4' 4'' 3
3 1 3 4'' 4'
Reply all
Reply to author
Forward
0 new messages