[Prévia] [Próxima] [Prévia por assunto] [Próxima por assunto]
[Índice cronológico]
[Índice de assunto]
RE: [MAC328]: Algoritmo de Boruvka
- Subject: RE: [MAC328]: Algoritmo de Boruvka
- From: Jose Coelho de Pina <coelho@ime.usp.br>
- Date: Tue, 17 Jun 2003 01:03:51 -0300
Antonio Jose Gonzales Alves writes:
> Eu não consegui inferir o consumo de tempo do Algoritmo de Boruvka em
> notação Theta....alguém poderia me ajudar?
Eu também não sei. Acho que primeiro precisamos pensar nas
estruturas de dados da implementação. O livro do Sedgewick
fala algo sobre um consumo de tempo de O(m log(n) log^*(m)).
Ele usa a estrutura union-find para representar conjuntos
disjuntos (vértices das árvores azuis).
coelho