Inzicht in tijdcomplexiteitsberekening voor Dijkstra-algoritme

Voor zover ik weet, heb ik de tijdscomplexiteit van het Dijkstra-algoritme berekend als big-O-notatie met behulp van de onderstaande lijst met aangrenzende gebieden. Het kwam er niet uit zoals het hoorde en daardoor begreep ik het stap voor stap.

1. Elk hoekpunt kan worden verbonden met (V-1) hoekpunten, vandaar dat het aantal aangrenzende randen van elk hoekpunt V – 1 is. Laten we zeggen dat E V-1 randen voorstelt die met elk hoekpunt zijn verbonden.
2. Zoeken & Het gewicht van elk aangrenzend hoekpunt in min heap bijwerken is O(log(V)) + O(1) of O(log(V)).
3. Vanaf stap1 en stap2 hierboven is de tijdscomplexiteit voor het bijwerken van alle aangrenzende hoekpunten van een hoekpunt E*(logV). of E*logV.
4. Daarom is de tijdcomplexiteit voor alle V-hoekpunten V * (E*logV), d.w.z. O(VElogV).

Maar de tijdcomplexiteit voor het Dijkstra-algoritme is O(ElogV). Waarom?

Antwoord 1, autoriteit 100%

Dijkstra’s kortste pad-algoritme is O(ElogV)waarbij:

• Vis het aantal hoekpunten
• Eis het totale aantal randen

Uw analyse is correct, maar uw symbolen hebben verschillende betekenissen! U zegt dat het algoritme O(VElogV)is waarbij:

• Vis het aantal hoekpunten
• Eis het maximale aantal randen dat aan een enkele knoop is bevestigd.

Laten we je Ehernoemen naar N. Dus de ene analyse zegt O(ElogV)en de andere zegt O(VNlogV). Beide zijn correct en in feite E = O(VN). Het verschil is dat ElogVeen strakkere schatting is.

Antwoord 2, autoriteit 11%

Een meer gedetailleerde uitleg toevoegen zoals ik het begreep, voor het geval dat:

• O(voor elk hoekpunt met min heap: voor elke rand lineair: duw hoekpunten naar min heap waar die rand naar wijst)
• V= aantal hoekpunten
• O(V * (pop vertex van min heap +vind niet-bezochte hoekpunten in randen *duw ze naar min heap))
• E= aantal randen op elk hoekpunt
• O(V * (pop vertex van min heap +E*duw niet-bezochte vertices naar min heap )). Merk op dat we hetzelfde knooppunt hier meerdere keren kunnen pushen voordat we het kunnen “bezoeken”.
• O(V * (log(heapgrootte) + E * log(heapgrootte)))
• O(V * ((E + 1) * log(hoopgrootte)))
• O(V * (E * log(hoopgrootte)))
• E = Vomdat elk hoekpunt kan verwijzen naar alle andere hoekpunten
• O(V * (V * log(hoopgrootte)))
• O(V^2 * log(hoopgrootte))
• heapgrootte is V^2omdat we ernaar streven elke keer dat we een afstand willen bijwerken en tot V-vergelijkingen kunnen hebben voor elk hoekpunt. bijv. voor het laatste hoekpunt, 1e hoekpunt heeft afstand 10, 2e heeft 9, 3e heeft 8, etc, dus we pushen elke keer om te updaten
• O(V^2 * log(V^2))
• O(V^2 * 2 * log(V))
• O(V^2 * log(V))
• V^2is ook een totaal aantal randen, dus als we E = V^2laten (zoals in de officiële naamgeving), krijgen we de O(E * log(V))

Antwoord 3, autoriteit 7%

laat n het aantal hoekpunten zijn en m het aantal randen.

Omdat je met Dijkstra’s algoritme O(n) delete-mins en O(m) decrease_keys hebt, die elk O(logn) kosten, de totale looptijd het gebruik van binaire hopen is O(log(n)(m + n)). Het is heel goed mogelijk om de kosten van decrease_keyaf te schrijven tot O(1) met behulp van Fibonacci-heaps, wat resulteert in een totale looptijd van O(nlogn+m), maar in de praktijk wordt dit vaak niet gedaan omdat de constante factorstraffen van FH’s zijn behoorlijk groot en in willekeurige grafieken is het aantal decrease_keys veel lager dan de respectieve bovengrens (meer in het bereik van O(n*log(m/n), wat veel beter op schaarse grafieken waar m = O(n)). Houd er dus altijd rekening mee dat de totale looptijd zowel afhankelijk is van uw gegevensstructuren als van de invoerklasse.

Antwoord 4, autoriteit 2%

In een dichte (of volledige) grafiek, E logV > V^2

Gelinkte data gebruiken & binaire hoop is niet altijd de beste.

In dat geval gebruik ik liever alleen matrixgegevens en bewaar ik de minimale lengte per rij.

Gewoon V^2tijd nodig.

In het geval dat E < V / logV.

Of, max. randen per hoekpunt is minder dan een constante K.

Gebruik dan binaire heap.

Antwoord 5

Laten we proberen het algoritme te analyseren zoals gegeven in het CLRS-boek.

voor elke lus in regel 7:voor elk hoekpunt zeg ‘u’ het aantal keren dat de lus loopt is gelijk aan het aantal aangrenzende hoekpunten van ‘u’.
Het aantal aangrenzende hoekpunten voor een knoop is altijd kleiner dan of gelijk aan het totale aantal randen in de grafiek.

Als we V (vanwege de while-lus in regel 4) en E (vanwege voor elk in regel 7) nemen en de complexiteit berekenen als VElog(V), zou het equivalent zijn aan aannemende dat elk hoekpunt E-randen heeft die erop invallen, maar in werkelijkheid zullen er maximaal of minder dan E-randen op een enkel hoekpunt vallen. (de hoogste E aangrenzende hoekpunten voor een enkel hoekpunt gebeuren in het geval van een stergrafiek voor het interne hoekpunt)

Antwoord 6

V:Aantal hoekpunten,
E:Aantal totale_randen
Stel dat de grafiek dicht is
De complexiteit zou zijn O(V*logV) + O( (1+2+…+V)*logV)

1+2+….+(V-1) = (v)*(v+1)/2 ~ V^2 ~ E omdat de grafiek dicht is
Dus de complexiteit zou O(ElogV) zijn.

De som 1+2+…+ V verwijst naar: Voor elk hoekpunt v in G.adj[u] maar niet in S
Als je aan Q denkt voordat een hoekpunt wordt geëxtraheerd, heeft het V hoekpunten, dan heeft het V-1 en dan V-2
… dan 1.