Časovna zahtevnost 2.kol

Question 1

Inicializacija

Answer 1

T(n) = O(|V|)

Question 2

operaciji vstavljanja in izločanja iz vrste/sklada za eno vozlišče

Answer 2

O(1)

Question 3

operaciji vstavljanja in izločanja iz vrste/sklada za vsa vozlišča

Answer 3

O(|V|)

Question 4

graf – seznami sosedov

Answer 4

T(n) = O(|V| + |E|)

Question 5

graf – matrika sosednosti

Answer 5

T(n) = O(|V|²)

Question 6

zmanjša za konstantni faktor

Answer 6

O(log₂ n)

Question 7

Evklidov algoritem

Answer 7

o(log₂(min(a, b)))

Question 8

urejanje z vrivanjem – zaporedje nepadajoče

Answer 8

T(n) = Ω(n)

Question 9

urejanje z vrivanjem – zaporedje padajoče in povprečno

Answer 9

T(n) = O(n²)

Question 10

preprosti problem nahrbtnika

Answer 10

T(n) = O(n)

Question 11

Primov algoritem

Answer 11

Θ(|V|²)

Question 12

Dijkstrin algoritem (s poljem)

Answer 12

O(|V|²)

Question 13

Dijkstrin algoritem (s kopico)

Answer 13

O(|E| · log₂ |V|)

Question 14

Dijkstrin algoritem (s Fibonaccijevo kopico)

Answer 14

O(|V| · log₂ |V| + |E|)

Question 15

Bellman-Fordov algoritem

Answer 15

O(|V| · |E|)

Question 16

Problem trgovskega potnika

Answer 16

O(nⁿ)

Question 17

Floyd–Warshall

Answer 17

Θ(n³)

Question 18

Bellman-Held-Karpov algoritem

Answer 18

T(n) = O(n² · 2ⁿ)

Question 19

optimalno dvojiško drevo

Answer 19

O(n³), lahko znižamo na O(n²)

Question 20

prostor rešitev (vračanje)

Answer 20

T(n) = O(p(n))

Question 21

Barvanje grafov

Answer 21

T(n) = O(n · mⁿ)