Primov algoritmus: Rozdiel medzi revíziami
Smazaný obsah Přidaný obsah
→Časová zložitost: preklepy |
preklepy |
||
Riadok 10:
** Pridaj ''v'' do V', pridaj (u,v) do E'
* Výstup: T(V',E') je minimálna kostra grafu
== Časová zložitost ==▼
{| class="wikitable"▼
! Dátová štruktúra s ohodnotením hrán !! Celková časová zložitosť▼
|-▼
| matica susednosti || O(n<sup>2</sup>)▼
|-▼
| [[binárna halda]] a ''zoznam susedov'' || O((n + m) log(n)) = n log(n)▼
|-▼
| [[Leonardo Pisano Fibonacci|Fibonacciho]] [[Halda (dátová štruktúra)|halda]] a ''zoznam susedov'' || O(m + n log(n))▼
|}▼
Jednoduchá implementácia s reprezentáciou grafu pomocou matice susednosti a prehľadávaním poľa ohodnotení má časovú zložitosť ''O(n<sup>2</sup>)''. S použitím binárnej haldy a zoznamu susedov dosiahneme zložitosť ''O(m log n)'', kde m je počet hrán a n je počet vrcholov. S použitím sofistikovanej Fibonacciho haldy zložitosť znížime až na ''O(m + n log n)'', čo je výhodné najmä pri grafoch, kde ''m'' je <math>\Omega(n log n)</math>.▼
== Príklad ==
Řádek 41 ⟶ 55:
|}
▲== Časová zložitost ==
▲{| class="wikitable"
▲! Dátová štruktúra s ohodnotením hrán !! Celková časová zložitosť
▲|-
▲| matica susednosti || O(n<sup>2</sup>)
▲|-
▲| [[binárna halda]] a ''zoznam susedov'' || O((n + m) log(n)) = n log(n)
▲|-
▲| [[Leonardo Pisano Fibonacci|Fibonacciho]] [[Halda (dátová štruktúra)|halda]] a ''zoznam susedov'' || O(m + n log(n))
▲|}
▲Jednoduchá implementácia s reprezentáciou grafu pomocou matice susednosti a prehľadávaním poľa ohodnotení má časovú zložitosť ''O(n<sup>2</sup>)''. S použitím binárnej haldy a zoznamu susedov dosiahneme zložitosť ''O(m log n)'', kde m je počet hrán a n je počet vrcholov. S použitím sofistikovanej Fibonacciho haldy zložitosť znížime až na ''O(m + n log n)'', čo je výhodné najmä pri grafoch, kde ''m'' je <math>\Omega(n log n)</math>.
| |||