Kjøretider

Question 1

Binærsøk

Answer 1

O(log(n))

Question 2

Binære søketrær oppslag, innsetting og sletting

Answer 2

O(n) værste tilfelle.

O(log(n)) om treet er balansert.

• Hvor n er antall noder i treet.

Question 3

AVL-trær oppslag, innsetting og sletting.

Answer 3

O(log(n))

• Hvor n er antall noder i treet.

Question 4

Binære heaps oppslag, innsetting og sletting

Answer 4

O(log(n))

Question 5

DFS

Answer 5

O(|V| + |E|)

Question 6

BFS

Answer 6

O(|V| + |E|)

Question 7

Topologisk sortering

Answer 7

O(|V| + |E|)

Question 8

Prims algoritme

Answer 8

O((|V| + |E|) * log(|V|) = O(|E| * log(|V|))

Question 9

Kruskals algoritme

Answer 9

O(|V| * log(|V|))

Question 10

Boruvkas algoritme

Answer 10

O((|V| + |E|) * log(|V|) = O(|E| * log(|V|))

Question 11

Djikstra

Answer 11

O((|V| + |E|) * log(|V|) = O(|E| * log(|V|))

Question 12

Bellman-Ford

Answer 12

O(|V| * |E|)

Question 13

Hopcroft-Tarjan

Answer 13

O(|V| + |E|)

Question 14

Sterkt sammenhengende komponenter (2xDFS)

Answer 14

O(|V| + |E|)

• Med anntagelse om at reversering av grafen er i kostant tid.

Question 15

Bubble sort

Answer 15

O(n^2)

Question 16

Selection sort

Answer 16

O(n^2)

Question 17

Insertion sort

Answer 17

O(n^2)

Spesielt rask på nesten sorterte arrayer, og blandt de raskeste på små arrayer.

Question 18

Heapsort

Answer 18

O(n * log(n))

Question 19

Merge sort

Answer 19

O(n * log(n))

Question 20

Quicksort

Answer 20

O(n^2) som værste, men dette skjer sjeldent

Som regel svært effektiv, med beste tiflelle O(n * log(n))

Question 21

Bucket sort

Answer 21

O(N + n)

N = antall bøtter
n = antall elementer

Question 22

Radix sort

Answer 22

Generelt er radix sort O(d(N + n))

d = antall bucket sorts
N = antall bøtter
n = antall elementer

Question 23

Hash maps

Answer 23

O(n) i værste tilfelle på alle operasjoner.

Med god hashfunksjon er forventet kjøretid O(1).