4.04 Classification Of Algorithms. Flashcards
Define computability:
Concerned with where a problem can or cannot be solved.
Define feasibility.
Concerned with how efficiently a problem can be solved.
What are the two standard measureS of the efficiency of an algorithm.
Space and time.
What is time?
How long the algorithm takes to execute.
What is space?
How much memory the algorithm uses for the storage of data during execution.
What happens when more than one algorithm exists which can solve a problem?
There is a trade off between time and space e.g. one solution may be quicker but requires more memory than another solution.
How do we measure efficiency?
The amount of space and time required varies depending on the number of inputs to the algorithm, therefore efficiency is normally expressed as a function of the number of inputs to an algorithm, commonly referred to as ‘n’.
How else can we measure efficiency.
Space complexity.
Time complexity:
processor clock speed
Efficiency of hardware implementation of
operations used.
Other processes executing concurrently.
How do we measure time complexity?
Using the big O notation, which allows us to focus on the algorithm rather than the hardware it is being executed on.
How can the order or magnitude of an algorithm be expressed?
As a function of it size.
What does a function map do?
A function maps one set of values onto another.
How do we express linear function?
f(x) = ax+c
How does fx increase?
In a straight line.
How do we express a polynomial function?
f(x) = axm + bx + c
How do we express an exponential function?
f(x) = ab^x
How do we express a logarithmic function?
f (x)= a logn x
(Little n)
What is a logarithm of a number?
The power that the base must be raised to to make it equal to the number.
What is the permutation of an object?
The permutation of a set of objects is the number of ways of arranging the objects within that set.
Outline an example of permutation.
Example : with 3 objects A,B,C, we can choose any to be the first object.
You then have two choices for the second object which gives use 3x2=6 possible permutations
ABC,ACB,BAC,BCA,CAB,CBA
What is formula for calculating the number of permutations n objects?
N factorial or expressed as n!
How is the time efficiency of an algorithm established?
Identify the basic operation that is performed by the algorithm.
Established how many times this operation is carried out as a function of the number of inputs (n).
Consider how quickly this value grows and identify the dominant part it this (e.g. in 4n^2+3 the dominant part is n^2 as it will have the most impact).
This is the order of complexity of the algorithm. It is written as as O(g) where g is the growth rate.
Linear time complexity algorithm example:
Algorithm for summing a list of numbers in a file:
TOTAL = 0 WHILE NOT at end of file READ Number from file Total = Total + number END WHILE PRINT TOTAL
What is the basic operation?
How many times is it carried out?
Som if a file contained n items, how many times would it be carried out?
What is the order complexity?
Total = Total + Number
It is in a loop, executed once for each number in the file.
So, if a file contained n items the basic operation would be executed n times.
The algorithm is said go have order complexity O(n)l
What else does the efficiency of some algorithms depend on?
The values of the inputs made to them.
