Unit 3 Flashcards
What two factors do computer scientists have to consider when creating an algorithm?
Time (number of steps) and space (memory needed)
What is a heuristic?
A reasonable time algorithm that provides an approximate solution to a problem. It’s “good enough”
- Finding routes between two towns
- Finding files in a list of docs
- Simulated annealing to solve TSP
Heuristic examples
Reasonable or non-reasonable time: O(1)
Reasonable
Reasonable or non-reasonable time: O(n)
Reasonable
Reasonable or non-reasonable time: O(n^2)
Reasonable
Reasonable or non-reasonable time: O(n^c)
Reasonable
Reasonable or non-reasonable time: O(log(n))
Reasonable
Reasonable or non-reasonable time: O(nlog(n))
Reasonable
Reasonable or non-reasonable time: O(c^n)
Non-reasonable
Reasonable or non-reasonable time: O(n!)
Non-reasonable
O(1)
Constant
O(n)
Linear
O(n^2)
Quadradic
O(n^c)
Polynomial