Kjøretider Flashcards
(50 cards)
1
Q
Insertion Sort Best-case
A
Theta(n)
2
Q
Insertion Sort Average-Case
A
Theta(n^2)
3
Q
Insertion sort worst-case
A
Theta(n^2)
4
Q
Merge sort best-case
A
Theta(nlgn)
5
Q
Merge sort average-case
A
Theta(n^2)
6
Q
Merge sort worst-case
A
Theta(nlgn)
7
Q
Selection sort best-case
A
Theta(n^2)
8
Q
Selection sort average case
A
Theta(n^2)
9
Q
Selection sort worst-case
A
Theta(n^2)
10
Q
Quicksort best-case
A
Theta(nlgn)
11
Q
Quicksort expected
A
Theta(nlgn)
12
Q
Quicksort worstcase
A
Theta(n^2)
13
Q
PARTITION
A
O(n)
14
Q
Randomized-quicksort best case
A
Theta(nlgn)
15
Q
Randomized Quicksort average
A
Theta(nlgn)
16
Q
Radomized quicksort worst case
A
Theta(n^2)
17
Q
Binærsøk best case
A
O(1)
18
Q
Binærsøk average
A
O(lgn)
19
Q
Binærsøk worstcase
A
O(lgn)
20
Q
«Brute force» average
A
O(n)
21
Q
Prims
A
O(E log V)
22
Q
Kruskal
A
O(E log V)
23
Q
Topologisk sortering
A
O(V + E)
24
Q
Bredde først søk
A
O(V+E)
25
Dybde først søk
O(V+E)
26
DAG -shortest path
Theta(V+E)
27
Dijkstea
O(E+V x log V)
28
Bellman-Ford
Theta(VxE)
29
Floyd Warhall
Theta(V^3)
30
Transitive closure
Theta(n^3) Finner ut om det finnes en sti mellom alle noder. Bruker boolean verdier, tar mindre plass
31
Ford-Fulkerson best case
O(VE^2)
32
Ford-Fulkerson worst
O(Ef), der f= maks flyt
33
Edmonds-Karp Worst
O(V x E^2)
| Bruker BFS som traversering
34
Build heap
O(n)
35
Min-heapify
O(n)
36
Insert average
O(1)
37
Insert worst
O(lgn)
38
Max-heapify worst
O(lgn)
39
Heap extract
O(lgn)
40
Heap increase key
O(lgn)
41
Heapsort average/best/worst
O(nlgn)
42
Bubble sort best
Theta(n)
43
Bubble sort average/worst
Theta(n^2)
44
Counting sort best/average/worst
Theta(n+k)
45
Radix sort average/best/worst
Theta(d(n+k))
46
Bucket sort best
Theta(n)
47
Bucket sort average
Theta(n)
48
Bucket sort worst case
Theta(n^2)
49
Select best/worst/average
Theta(n)
Siden worst case er lineær og det er fysisk umulig å gjøre det bedre enn det så må automatism best og average case også være det
50
Randomizes select worst
Theta(n^2)
