Árvore de extensão mínima: diferenças entre revisões

O mais rápido algoritmo de árvore mínima de extensão foi desenvolvido por [[Bernard Chazelle]], e foi baseado no algoritmo de Borůvka's. Ele roda em um tempo de ''[[notação O |O]]''(''m'' α(''m'',''n'')), onde ''m'' é o número de arestas, ''n'' refere-se ao numero de vértices e α é a clássica função inversa da [[função de Ackermann]]. A função α cresce de forma extremamente lenta, então para todos os propósitos práticos ele pode ser considerado uma constante não maior que quatro; portanto o algoritmo de Chazelle chega muito perto de um tempo ''O''(''m'').

 

[[Categoria:Algoritmos]]