Algoritmo Tempo Complexidade de Prim

StackOverflow https://stackoverflow.com/questions/716341

Pergunta

Eu estava olhando para o Wikipedia entrada para o algoritmo de Prim e notei que seu tempo complexidade com uma matriz de adjacência é o (V ^ 2) e a sua complexidade de tempo com uma lista montão e de adjacência é o (e lg (V)) onde e é o número de arestas e V é o número de vértices no gráfico.

Uma vez que o algoritmo de Prim é usado em gráficos mais densas, E pode aproximar V ^ 2, mas quando o faz, a complexidade de tempo com uma pilha torna-se O (V ^ 2 lg (V)), que é maior que O (V ^ 2 ). Obviamente, um monte vai melhorar o desempenho ao longo apenas procurar a matriz, mas a complexidade de tempo diz o contrário.

Como o algoritmo realmente retardar com uma melhoria?

Foi útil?

Solução

Mesmo que a pilha evita que você procura através da matriz, ele diminui a parte "update" do algoritmo: atualizações matriz são O (1), enquanto as atualizações heap são O (log (N))

Em essência, você troca velocidade em uma parte do algoritmo de velocidade em outra.

Não importa o que, você tem que procurar N vezes. No entanto, em grafos densos, você precisa atualizar um lote (~ V ^ 2), e em grafos esparsos, você não.

Outro exemplo em cima da minha cabeça está à procura de elementos em uma matriz. Se você está fazendo isso apenas uma vez, busca linear é a melhor -. Mas se você fizer muitas consultas, é melhor para classificá-lo e utilização binária procurar cada vez

Outras dicas

A partir da Introdução aos Algoritmos (Carmen)

Tempo = T (V) · T (EXTRACT-MIN) + T (E) · T (REDUÇÃO-CHAVE) 

                   T(EXTRACT-MIN)   T(DECREASE-KEY)   Total

1. array            O(V)             O(1)              O(V^2)
2. binary heap      O(lgV)           O(lgV)            O(E lgV)
3. Fibonacci heap   O(lgV)           O(1)              O(E + VlgV)

Usando diferentes estruturas de dados faz com que diferentes complexidades de tempo.

Eu acho que você leu errado em algum grau. Para gráficos densas, as artigo fala sobre a utilização de aterros de Fibonacci com complexidade O (E + V log V), o que é significativamente melhor.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top