Kjøretider Flashcards
Binærsøk
O(log(n))
Binære søketrær oppslag, innsetting og sletting
O(n) værste tilfelle.
O(log(n)) om treet er balansert.
- Hvor n er antall noder i treet.
AVL-trær oppslag, innsetting og sletting.
O(log(n))
- Hvor n er antall noder i treet.
Binære heaps oppslag, innsetting og sletting
O(log(n))
DFS
O(|V| + |E|)
BFS
O(|V| + |E|)
Topologisk sortering
O(|V| + |E|)
Prims algoritme
O((|V| + |E|) * log(|V|) = O(|E| * log(|V|))
Kruskals algoritme
O(|V| * log(|V|))
Boruvkas algoritme
O((|V| + |E|) * log(|V|) = O(|E| * log(|V|))
Djikstra
O((|V| + |E|) * log(|V|) = O(|E| * log(|V|))
Bellman-Ford
O(|V| * |E|)
Hopcroft-Tarjan
O(|V| + |E|)
Sterkt sammenhengende komponenter (2xDFS)
O(|V| + |E|)
- Med anntagelse om at reversering av grafen er i kostant tid.
Bubble sort
O(n^2)
Selection sort
O(n^2)
Insertion sort
O(n^2)
Spesielt rask på nesten sorterte arrayer, og blandt de raskeste på små arrayer.
Heapsort
O(n * log(n))
Merge sort
O(n * log(n))
Quicksort
O(n^2) som værste, men dette skjer sjeldent
Som regel svært effektiv, med beste tiflelle O(n * log(n))
Bucket sort
O(N + n)
N = antall bøtter n = antall elementer
Radix sort
Generelt er radix sort O(d(N + n))
d = antall bucket sorts N = antall bøtter n = antall elementer
Hash maps
O(n) i værste tilfelle på alle operasjoner.
Med god hashfunksjon er forventet kjøretid O(1).
