Tijdcomplexiteit van Prims Algoritme?

Ik vond de tijd complexiteit van Prims Algoritme overal als O ((v + e) ​​log v) = e log v . Maar zoals we het algoritme kunnen zien:

Het lijkt alsof de tijdcomplexiteit o (v (log v + e log v) is. Maar als de tijdcomplexiteit o ((v + e) ​​log v) is. Dan moeten de nesting zo moeten zijn:

Maar het bovenstaande nestelen lijkt fout te zijn.

Antwoord 1, Autoriteit 100%

MST-PRIM(G, w, r)
1  for each u ∈ G.V
2       u.key ← ∞
3       u.π ← NIL
4   r.key ← 0
5   Q ← G.V
6   while Q ≠ Ø
7       u ← EXTRACT-MIN(Q)
8       for each v ∈ G.Adjacent[u]
9           if v ∈ Q and w(u, v) < v.key
10              v.π ← u
11              v.key ← w(u, v)

met behulp van een binair hoop

1. De tijdcomplexiteit vereist voor één oproep naar EXTRACT-MIN(Q)is O(log V)met behulp van een MIN-prioritaire wachtrij. De while-lus op regel 6 uitvoert de totale v-kalen.so EXTRACT-MIN(Q)wordt Vtijden genoemd. Dus de complexiteit van EXTRACT-MIN(Q)is O(V logV).

2. De forlus op regel 8 is het uitvoeren van totaal 2Etijden als lengte van elke registratielijsten is 2Evoor een ongerichte grafiek . De tijd die nodig is om lijn 11 uit te voeren, is O(log V)door gebruik te maken van de DECREASE_KEYWERKING op de MIN-heap. Lijn 11 voert ook totaal 2ETIJDEN uit. Dus de totale tijd die nodig is om regel 11 uit te voeren O(2E logV) = O(E logV).

3. De for-lus op regel 1 wordt Vkeer uitgevoerd. Het gebruik van de procedure om regel 1 tot 5 uit te voeren vereist een complexiteit van O(V).

Totale tijdcomplexiteit van MST-PRIMis de som van de tijdcomplexiteit die nodig is om stap 1 tot en met 3 uit te voeren voor een totaal van O(VlogV + (E logV + V) = O(E logV).

Een Fibonacci-hoop gebruiken

1. Hetzelfde als hierboven.
2. Het uitvoeren van regel 11 vereist afgeschreven tijd van O(1). Regel 11 voert in totaal 2Ekeer uit. Dus de totale tijdcomplexiteit is O(E).
3. Hetzelfde als hierboven

Dus de totale tijdcomplexiteit van MST-PRIMis de som van het uitvoeren van stappen 1 tot en met 3 voor een totale complexiteit van O(V logV + E + V)=O(E + V logV).

Antwoord 2, autoriteit 16%

Uw idee lijkt correct. Laten we de complexiteit nemen als:
V(lg(v) + E(lg(v)))
Merk dan op dat we in de binnenste for-lus eigenlijk door alle hoekpunten gaan, en niet door de rand, dus laten we een beetje aanpassen om
V(lg(v) + V(lg(v)))
wat betekent
V(lg(v)) + V*V(lg(v))
Maar voor analyse in het slechtste geval (dichte grafieken) is V * V ongeveer gelijk aan het aantal randen, E
V(lg(v)) + E(lg(v))
(V+E((lg(v))
maar aangezien V << E, vandaar
E(lg(v))

Antwoord 3, autoriteit 13%

De tijdscomplexiteit van het algoritme van Prim is O(VlogV + ElogV). Het lijkt erop dat je begrijpt hoe de VlogVis ontstaan, dus laten we dat overslaan. Dus waar komt ElogVvandaan? Laten we beginnen met te kijken naar de broncode van het algoritme van Prim:

 | MST-PRIM(Graph, weights, r)
1 |  for each u ∈ Graph.V
2 |       u.key ← ∞
3 |       u.π ← NIL
4 |   r.key ← 0
5 |   Q ← Graph.V
6 |   while Q ≠ Ø
7 |       u ← EXTRACT-MIN(Q)
8 |       for each v ∈ Graph.Adj[u]
9 |           if v ∈ Q and weights(u, v) < v.key
10|               v.π ← u
11|               v.key ← weights(u, v)

Regels 8-11 worden uitgevoerd voor elk element in Q, en we weten dat er V-elementen zijn in Q(die de set vertegenwoordigen van alle hoekpunten). De lus van regel 8 itereert door alle buren van het momenteel geëxtraheerde hoekpunt; we zullen hetzelfde doen voor het volgende geëxtraheerde hoekpunt, en voor het volgende. Het algoritme van Djistkra herhaalt geen hoekpunten (omdat het een hebzuchtig, optimaal algoritme is), en zal ons uiteindelijk door elk van de verbonden hoekpunten laten gaan en al hun buren onderzoeken. Met andere woorden, deze lus zal op een gegeven moment tweemaal door alle randen van de grafiek gaan (2E).

Waarom twee keer? Want op een gegeven moment komen we uit de andere richting terug op een eerder onderzochte rand, en we kunnen het niet uitsluiten totdat we het daadwerkelijk hebben gecontroleerd. Gelukkig valt die constante 2weg tijdens onze tijdcomplexiteitsanalyse, dus de lus doet eigenlijk gewoon Eveel werk.

Waarom was het niet V*V? Je zou die term kunnen bereiken als je bedenkt dat we elk hoekpunt en zijn buren moeten controleren, en in het ergste geval het aantal buren in de buurt van Vmoeten brengen. Inderdaad, in een dichte grafiek V*V = E. Maar de nauwkeurigere beschrijving van het werk van deze twee lussen is “twee keer door alle randen gaan”, dus verwijzen we in plaats daarvan naar E. Het is aan de lezer om te verbinden hoe schaars hun grafiek is met de tijdscomplexiteit van deze term.

Laten we eens kijken naar een kleine voorbeeldgrafiek met 4 hoekpunten:

   1--2
    |\ |
    | \|
    3--4

Stel dat Qons de knooppunten geeft in de volgorde 1, 2, 3 en dan 4.

• In de eerste iteratie van de buitenste lus wordt de binnenste lus 3 keer uitgevoerd (voor 2, 3 en 4).
• In de tweede iteratie van de buitenste lus wordt de binnenste lus 2 keer uitgevoerd (voor 1 en 4).
• In de derde iteratie van de buitenste lus wordt de binnenste lus 2 keer uitgevoerd (voor 1 en 4).
• In de laatste iteratie van de buitenste lus wordt de binnenste lus 3 keer uitgevoerd (voor 1, 2 en 3).

Het totale aantal herhalingen was 10, wat tweemaal het aantal randen is (2*5).

Het extraheren van het minimum en het volgen van de bijgewerkte minimumranden (meestal gedaan met een Fibonacci-heap, resulterend in log(V)tijdcomplexiteit) vindt plaats binnen de lus-iteraties – de exacte mechanismen houden in dat komen binnen de binnenste lus vaak genoeg voor dat ze worden gecontroleerd door de tijdcomplexiteit van beide lussen. Daarom is de volledige tijdcomplexiteit voor deze fase van het algoritme O(2*E*log(V)). Het laten vallen van de constante levert O(E*log(V))op.

Aangezien de totale tijdcomplexiteit van het algoritme O(VlogV + ElogV)is, kunnen we vereenvoudigen tot O((V+E)logV). In een dichte grafiek E > V, dus we kunnen O(ElogV)concluderen.

Antwoord 4, autoriteit 5%

eigenlijk, zoals u zegt, is binnen genest, terwijl tijdcomplexiteit v.E lg V zou moeten zijn in het geval van asymptotische analyse. Maar in Cormen hebben ze een afgeschreven analyse gedaan, daarom blijkt het zo te zijn (Elogv)