121 Week 11 - Complexity Flashcards
Algorithm
An effective method for solving a class of problems.
Consists of a finite length input, an effective method made up of a finite list of instructions and an output which is produced by the effective method.
Key types of algorithms
Sorting algorithms: Used to sort the data in a particular format.
Searching algorithms: Used to find a value or record that user requests.
Graph Algorithms: Used to find solutions to problems such as finding the shortest path between cities.
How can algorithms be compared
Time and space complexity.
What resources to algorithms require
Space: the amount of memory required to solve the problem.
Time: how many steps relative to input size it takes to solve the problem.
Algorithms need to be space and time efficient because these are not unlimited resources.
Qualities of a good algorithm
Performance, correctness, robustness, and simplicity.
Space complexity
The amount of memory required by an algorithm to run to completion.
How is space complexity split up
Fixed part: The size required to store certain data/variables, that is independent of the size of the problem.
Variable part: Space needed by variables, whose size is dependent on the size of the problem.
Time complexity
Runtime: how long it takes for the algorithm to compute a solution.
Runtime depends on the size and organisation of the input.
In general the upper bound/worst case runtime is looked for.
Optimal algorithm
An optimal algorithm uses the least amount of space and executes as fast as possible.
However this is not always possible as there are usually trade-offs between space and time complexity meaning one is usually prioritized.
Priority between space and time complexity
Because of current hardware technologies, space complexity is not as essential as most machines have enough memory to run the algorithm.
Time complexity is now more of a priority.
