Primov algoritmus: Rozdiel medzi revíziami
Smazaný obsah Přidaný obsah
wikilinky |
aktualizácia |
||
Riadok 40:
|Teraz sú už vybrané všetky vrcholy a teda sme získali minimálnu kostru grafu (vyznačená zelenou farbou). Celková váha kostry je 39.
|}
== Časová zložitost ==
{| class="wikitable"
! Datová struktura s ohodnocením hran !! Celková [[Asymptotická složitost|časová složitost]]
|-
| [[matica susednosti]] || n<sup>2<sup>
|-
| [[binární halda]] (v pseudokódu níže) a ''seznam sousedů'' || O((n + m) log(n)) = n log(n)
|-
| [[Fibonacciho halda]] a ''seznam sousedů'' || m + n log(n)
|}
Jednoduchá implementace s použitím reprezentace grafu pomocí [[matice sousednosti]] a prohledáváním pole cen má [[Asymptotická složitost|časovou složitost]] ''O(n<sup>2</sup>)''. S použitím [[binární halda|binární haldy]] a seznamu sousedů dosáhneme složitosti ''O(m log n)'', kde m je počet hran a n je počet vrcholů. S použitím sofistikované [[Fibonacciho halda|Fibonacciho haldy]] složitost snížíme až na ''O(m + n log n)'', což je obzvláště rychlé u grafů, kde ''m'' je <math>\Omega(n log n)</math>.
| |||