Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algoritmer og Datastrukturer > Kjøretider > Flashcards

Kjøretider Flashcards

1
Q

Insertion Sort Best-case

A

Theta(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Insertion Sort Average-Case

A

Theta(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Insertion sort worst-case

A

Theta(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Merge sort best-case

A

Theta(nlgn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Merge sort average-case

A

Theta(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Merge sort worst-case

A

Theta(nlgn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Selection sort best-case

A

Theta(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Selection sort average case

A

Theta(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Selection sort worst-case

A

Theta(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Quicksort best-case

A

Theta(nlgn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Quicksort expected

A

Theta(nlgn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Quicksort worstcase

A

Theta(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

PARTITION

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Randomized-quicksort best case

A

Theta(nlgn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Randomized Quicksort average

A

Theta(nlgn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Radomized quicksort worst case

A

Theta(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Binærsøk best case

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Binærsøk average

A

O(lgn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Binærsøk worstcase

A

O(lgn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

«Brute force» average

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
Q

Dybde først søk

A

O(V+E)

26
Q

DAG -shortest path

A

Theta(V+E)

27
Q

Dijkstea

A

O(E+V x log V)

28
Q

Bellman-Ford

A

Theta(VxE)

29
Q

Floyd Warhall

A

Theta(V^3)

30
Q

Transitive closure

A

Theta(n^3) Finner ut om det finnes en sti mellom alle noder. Bruker boolean verdier, tar mindre plass

31
Q

Ford-Fulkerson best case

A

O(VE^2)

32
Q

Ford-Fulkerson worst

A

O(Ef), der f= maks flyt

33
Q

Edmonds-Karp Worst

A

O(V x E^2)

Bruker BFS som traversering

34
Q

Build heap

A

O(n)

35
Q

Min-heapify

A

O(n)

36
Q

Insert average

A

O(1)

37
Q

Insert worst

A

O(lgn)

38
Q

Max-heapify worst

A

O(lgn)

39
Q

Heap extract

A

O(lgn)

40
Q

Heap increase key

A

O(lgn)

41
Q

Heapsort average/best/worst

A

O(nlgn)

42
Q

Bubble sort best

A

Theta(n)

43
Q

Bubble sort average/worst

A

Theta(n^2)

44
Q

Counting sort best/average/worst

A

Theta(n+k)

45
Q

Radix sort average/best/worst

A

Theta(d(n+k))

46
Q

Bucket sort best

A

Theta(n)

47
Q

Bucket sort average

A

Theta(n)

48
Q

Bucket sort worst case

A

Theta(n^2)

49
Q

Select best/worst/average

A

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
Q

Randomizes select worst

A

Theta(n^2)

Algoritmer og Datastrukturer (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions