Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

Obě strany předchozí revize Předchozí verze
Následující verze
Předchozí verze
mgr-szz:in-pds:1-pds [2019/06/15 14:45]
lachmanfrantisek
mgr-szz:in-pds:1-pds [2020/04/12 16:56] (aktuální)
Řádek 140: Řádek 140:
 </​box>​ </​box>​
  
-^ algoritmus ^ složitost ^ typ grafu ^+^ algoritmus ​(1-to-n)^ složitost ^ typ grafu ^
 | BFS | <​math>​\mathcal{O}(m+n)</​math>​ | vzdálenost = počet hran | | BFS | <​math>​\mathcal{O}(m+n)</​math>​ | vzdálenost = počet hran |
-| Dijkstrův algoritmus | <​math>​\mathcal{O}(m * \log n)</​math>​ | nezáporné délky hran |+| Dijkstrův algoritmus | <​math>​\mathcal{O}(m ​+ n * \log n)</​math>​ | nezáporné délky hran |
 | Bellman-Ford | <​math>​\mathcal{O}(m * n)</​math>​| | | Bellman-Ford | <​math>​\mathcal{O}(m * n)</​math>​| |
 +
 +^ algoritmus (n-to-n)^ složitost ^ typ grafu ^
 | Násobení matic | <​math>​\mathcal{O}(n^3 * \log n)</​math>​ | | | Násobení matic | <​math>​\mathcal{O}(n^3 * \log n)</​math>​ | |
 | Floyd-Warshall | <​math>​\mathcal{O}(n^3)</​math>​ | | | Floyd-Warshall | <​math>​\mathcal{O}(n^3)</​math>​ | |
Řádek 158: Řádek 160:
   * inicializace O(n), naplnění Q O(n), zpracování všech vrcholů O(n), relaxace všech hran O(m) + aktualizace hodnot v Q O(log n) pro každou hranu   * inicializace O(n), naplnění Q O(n), zpracování všech vrcholů O(n), relaxace všech hran O(m) + aktualizace hodnot v Q O(log n) pro každou hranu
   * uvažujeme binární haldu, kde vložení je v průměru v O(1), odstranění minima O(log n) a aktualizace O(log n)   * uvažujeme binární haldu, kde vložení je v průměru v O(1), odstranění minima O(log n) a aktualizace O(log n)
-  ​* = O(m * log n)+    ​* = O(m * log n) 
 +  * s využitím fibonacciho haldy: O(m + n * log n)
  
 **Korektnost** **Korektnost**
mgr-szz/in-pds/1-pds.1560602725.txt.gz · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)
Nahoru
CC Attribution-Noncommercial-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0