4.4.4 Classification of algorithms Flashcards
How can algorithms be compared?
1) Algorithms can be compared on how long it takes them to solve a problem
2) Known as time-complexity
What is execution time and how is it important?
1) Execution time is important as the faster an algorithm can be solved the better
2) Faster execution time reduces the financial impact
Why is space important for the efficiency of an algorithm?
1) An algorithm that takes up less space (memory) is better
2) Less RAM is used up
3) More algorithms can be run on the same hardware and this increases productivity
Why is efficiently implementing algorithms important?
1) Taking up minimal amounts of resources and running algorithms at high speeds is important for data sets such as Big Data
What is a function?
1) A mapping from one set of values (domain) to another set of values (co-domain)
2) E.g. ℕ → ℕ.
What is a linear function?
1) A Straight line graph
2) E.g. f(x) = 2x and f(x) = 7x + 1
What is a polynomial function?
1) E.g. Uses Quadratics and cubics
2) f(x) = 5x2
3)
What is a Exponential function?
1) Function where input value exponentially increases rapidly
What is a Logarithmic function?
1) Function involving the calculation of the logarithm of the input
2) E.g. log2(x)
What is meant by permutation of a set of objects?
1) A permutation is the number of ways of arranging the object
2) E.g. 3 objects A, B, C to choose the first object there are 3 choices, 2 choices for 2nd object
3) 3 x 2 = 6 ways to arrange the first two objects and one way for the third object
How do you calculate the permutations of an object?
1) Written in factorial so for four objects it would be 4!
2) For 6 objects = 6 x 5 x 4 x 3 x 2 x 1
What is Big-O Notation and how many different time complexities are there and what are they?
1) Big-O notation is used to express the time complexity or performance of an algorithm ( 0 stands for order)
- constant time
- logarithmic time
- linear time
- polynomial time
- exponential time
- Factorial
What does O(1) represent?
1) Constant time: Same time to execute irrespective of the size of the input
E.g. length
What does O(n) represent?
1) Linear time: Performance grows in linear time directly proportionate to the size of the data set
2) 1000 unsorted items will take 1000 times longer than searching an array for 1 item
What does O( log n) represent?
1) Logarithmic time complexity
2) The time taken to execute an algorithm of order O(log n) grows slowly as the data set size increases