Časovna zahtevnost 2.kol Flashcards
(21 cards)
Inicializacija
T(n) = O(|V|)
operaciji vstavljanja in izločanja iz vrste/sklada za eno vozlišče
O(1)
operaciji vstavljanja in izločanja iz vrste/sklada za vsa vozlišča
O(|V|)
graf – seznami sosedov
T(n) = O(|V| + |E|)
graf – matrika sosednosti
T(n) = O(|V|²)
zmanjša za konstantni faktor
O(log₂ n)
Evklidov algoritem
o(log₂(min(a, b)))
urejanje z vrivanjem – zaporedje nepadajoče
T(n) = Ω(n)
urejanje z vrivanjem – zaporedje padajoče in povprečno
T(n) = O(n²)
preprosti problem nahrbtnika
T(n) = O(n)
Primov algoritem
Θ(|V|²)
Dijkstrin algoritem (s poljem)
O(|V|²)
Dijkstrin algoritem (s kopico)
O(|E| · log₂ |V|)
Dijkstrin algoritem (s Fibonaccijevo kopico)
O(|V| · log₂ |V| + |E|)
Bellman-Fordov algoritem
O(|V| · |E|)
Problem trgovskega potnika
O(nⁿ)
Floyd–Warshall
Θ(n³)
Bellman-Held-Karpov algoritem
T(n) = O(n² · 2ⁿ)
optimalno dvojiško drevo
O(n³), lahko znižamo na O(n²)
prostor rešitev (vračanje)
T(n) = O(p(n))
Barvanje grafov
T(n) = O(n · mⁿ)
