Time and Space Complexity
Lição 7 de 9 do curso Algoritmo de Prim - Algoritmos de Grafos da Coddy.
Complexidade de Tempo:
- A versão de varredura de arestas aqui é O(V * E): V-1 rodadas, cada uma varrendo todas as E arestas. Com um heap binário e listas de adjacência, o Prim roda em O((V + E) log V).
Complexidade de Espaço:
- O(V) para o array
inTree(além das arestas de entrada).
Resumo:
- O Prim expande uma árvore, sempre adicionando a aresta mais barata que sai dela, até que todos os vértices sejam incluídos.
- Ele produz o mesmo peso total mínimo que o Kruskal, usando uma estratégia diferente.
Experimente você mesmo
Esta lição não inclui um desafio de código.
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Algoritmo de Prim - Algoritmos de Grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity