Clustering: diferenças entre revisões

Implementar este algoritmo consiste em descobrir uma maneira eficiente de encontrar a aresta menos custosa dentro de um subconjunto de arestas do grafo original - para construir a minimum spanning tree - e a mais custosa - para deletá-la na segunda etapa do algoritmo. Tais operações são facilmente realizadas com o uso de uma fila de prioridades que pode ser mantida com complexidade <math>O(logm)</math>, onde m é o número de elementos na fila.

A complexidade de montar a minimum spanning tree é <math>O(nlogm)</math>, onde <math>n</math> é o número de nós no grafo e <math>m</math> o número de arestas. Já a complexidade de deletar k-1 arestas é <math>O((k-1)log(n-1))</math>. Logo, o tempo de execução é dominado pela construção da minimum spanning tree. Conclui-se, então, que encontrar k clusters em um grafo <math>U</math> com <math>n</math> nós e arestas é uma tarefa que possuí tempo de execução <math>O(nlogm)</math>.

 

(require data/heap)