Algorithms Flashcards
1
Q
Sum of triangular numbers complexity
A
1/2n(n-1)
Therefore quadratic
2
Q
First fit
A
Pack each box in turn into first available bin into which it will fit
- complexity = quadratic.
3
Q
First fit decreasing
A
- reorder largest to smallest
- apply first fit
- complexity = quadratic
4
Q
Full bin
A
- look for combos yourself
- not an algorithms because it is ambiguous - is heuristic
5
Q
quick sort
A
Pivot number compared to every number, slide all numbers less than it to the left of it, in the same order they were
- quadratic complexity in worst case
6
Q
Algorithms are
A
- unambiguous
- deterministic
- finite
7
Q
Heuristic algorithm definition
A
- will usually find a good solution although not necessarily an optimal solution
8
Q
Bubble sort shuttle sort complexity
A
Quadratic
9
Q
Put values less than or equal to the pivot
A
to the left of the pivot
