Kjøretider Flashcards
Insertion Sort Best-case
Theta(n)
Insertion Sort Average-Case
Theta(n^2)
Insertion sort worst-case
Theta(n^2)
Merge sort best-case
Theta(nlgn)
Merge sort average-case
Theta(n^2)
Merge sort worst-case
Theta(nlgn)
Selection sort best-case
Theta(n^2)
Selection sort average case
Theta(n^2)
Selection sort worst-case
Theta(n^2)
Quicksort best-case
Theta(nlgn)
Quicksort expected
Theta(nlgn)
Quicksort worstcase
Theta(n^2)
PARTITION
O(n)
Randomized-quicksort best case
Theta(nlgn)
Randomized Quicksort average
Theta(nlgn)
Radomized quicksort worst case
Theta(n^2)
Binærsøk best case
O(1)
Binærsøk average
O(lgn)
Binærsøk worstcase
O(lgn)
«Brute force» average
O(n)
Prims
O(E log V)
Kruskal
O(E log V)
Topologisk sortering
O(V + E)
Bredde først søk
O(V+E)
Dybde først søk
O(V+E)
DAG -shortest path
Theta(V+E)
Dijkstea
O(E+V x log V)
Bellman-Ford
Theta(VxE)
Floyd Warhall
Theta(V^3)
Transitive closure
Theta(n^3) Finner ut om det finnes en sti mellom alle noder. Bruker boolean verdier, tar mindre plass
Ford-Fulkerson best case
O(VE^2)
Ford-Fulkerson worst
O(Ef), der f= maks flyt
Edmonds-Karp Worst
O(V x E^2)
Bruker BFS som traversering
Build heap
O(n)
Min-heapify
O(n)
Insert average
O(1)
Insert worst
O(lgn)
Max-heapify worst
O(lgn)
Heap extract
O(lgn)
Heap increase key
O(lgn)
Heapsort average/best/worst
O(nlgn)
Bubble sort best
Theta(n)
Bubble sort average/worst
Theta(n^2)
Counting sort best/average/worst
Theta(n+k)
Radix sort average/best/worst
Theta(d(n+k))
Bucket sort best
Theta(n)
Bucket sort average
Theta(n)
Bucket sort worst case
Theta(n^2)
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
Randomizes select worst
Theta(n^2)
