MST: complexidade do algoritmo de Prim, por que não

8

De acordo com o CLRS, os algoritmos do Prim são implementados como abaixo -

MST-PRIM(G,w,r)

  • para cada uV[G] Faz
    • key[u]
    • π[u]NIL
  • key[r]0
  • QV[G]
  • enquanto Q Faz // ... O(V)
    • u EXTRACT-MIN(u) // ... O(lgV)
      • para cada vadj[u] Faz // ... O(E)
        • E se vQ e w(u,v)>key[v]
          • então π[v]u
            • keyw(u,v) // DECREASE-KEY ... O(lgV)

O livro diz que a complexidade total é O(VlgV+ElgV)O(ElgV). No entanto, o que entendi é que o forloop interno com a DECREASE-KEYoperação custaráO(ElgV), e o whileloop externo inclui EXTRACT-MINo forloop interno e o interno , portanto, a complexidade total deve serO(V(lgV+ElgV))=O(VlgV+EVlgV)O(EVlgV).

Por que a análise de complexidade não é realizada como tal? e O que há de errado com minha formulação?

ramgorur
fonte

Respostas:

9

A complexidade é derivada da seguinte maneira. Os custos da fase de inicializaçãoO(V). owhile loop é executado |V|vezes. ofor loop aninhado dentro do while loop é executado degree(u)vezes. Finalmente, o lema do aperto de mão implica que existemΘ(E)implícitas DECREASE-KEY's. Portanto, a complexidade é:Θ(V)TEXTRACTMIN+Θ(E)TDECREASEKEY.

A complexidade real depende da estrutura de dados realmente usada no algoritmo. Usando uma matriz,TEXTRACTMIN=O(V),TDECREASEKEY=O(1)complexidade é O(V2) no pior dos casos.

Usando uma pilha binária, TEXTRACTMIN=O(logV),TDECREASEKEY=O(logV)complexidade é O(ElogV)no pior dos casos. Aqui está o porquê: como o gráfico está conectado, então|E||V|1e E é no máximo V2(na pior das hipóteses, para um gráfico denso). Provavelmente, você perdeu esse ponto.

Usando uma pilha de Fibonacci, TEXTRACTMIN=O(logV) amortizado, TDECREASEKEY=O(1) amortizado, a complexidade é O(E+VlogV) no pior dos casos.

Massimo Cafaro
fonte
1

Sua ideia parece correta. Vamos considerar a complexidade como V(lgv+Elgv). Então observe que no loop for interno, estamos passando por todos os vértices, e não pelas arestas, então vamos modificar um pouco para V(lgv+Vlgv), que significa Vlgv+V2lgv. Mas, para a análise do pior caso (gráficos densos),V2 é aproximadamente igual ao número de arestas, Edando Vlgv+Elgv=(V+E)lgv mas desde VE, conseqüentemente Elgv.

user3473400
fonte
O que é v? Um erro de digitação paraV?
precisa saber é o seguinte
Na verdade, eu não entendo nada disso. O que significa dizer "Vamos considerar a complexidade como [expressão 1]" e depois "modificar um pouco para [expressão 2]"? Você não pode simplesmente assumir que o tempo de execução é uma coisa e depois mudar para outra.
David Richerby