Hey guys! How're you doing!
Today we will go through another conceptual topic of Algorithms and the related terminologies like Space-Time Tradeoff and Complexity of an algorithm. Hence lets get started!
Algorithms
An algorithm is a well defined list of steps for solving a particular problem. Starting from an initial state, an algorithm states the instructions needed to describe a computation that proceeds through a well-defined series of successive states, eventually terminating in a final ending state. There may be more than one algorithm to solve a particular problem.Given below is an algorithm gives the required steps required by a temperature sensor to measure and display temperature on an attached LED screen.
Complexity and Space-Time Tradeoff
The complexity of an algorithm is the function which gives the running time and/ or space in term of input size. In simple words, the complexity of an algorithm refers to how fast or slow a particular algorithm performs. We define complexity as a numerical function T(n) - time versus the input size n.Further, each of our algorithm will involve a particular data structure. Accordingly we may not always be able to use the most efficient algorithm, since the choice of data structure depends on many things including the type of data and the frequency with which various data operations are applied.
How to find the complexity of an algorithm?
Let us understand this with the help of an example. Suppose we are implementing an algorithm that helps us to search for an record amongst a list of records. We can have the following three cases which relate to the relative success our algorithm can achieve with respect to time:
- Best Case: The record we are trying to search is the first record of the list. If f(n) is the function which gives the running time and/ or storage space requirement of the algorithm in terms of the size n of the input data, this particular case of the algorithm will produce a complexity C(n)=1 for our algorithm f(n) as the algorithm will run only 1 time until it finds the desired record.
- Worst Case: The record we are trying to search is the last record of the list. If f(n) is the function which gives the running time and/ or storage space requirement of the algorithm in terms of the size n of the input data, this particular case of the algorithm will produce a complexity C(n)=n for our algorithm f(n) as the algorithm will run n times until it finds the desired record.
- Average Case: The record we are trying to search can be any record in the list. In this case we do not know at which position it might be. Hence we take an average of all the possible times our algorithm may run. Hence assuming for n data, we have a probability of finding any one of them is 1/n. Multiplying each of these with the number of times our algorithm might run for finding each of them and then taking a sum of all those multiples, we can obtain the complexity C(n) for our algorithm f(n) in case of an average case as following:
.png)
.png)
.png)
Hence in this way, we can find the complexity of an algorithm.
- Space Complexity: It is also known as memory requirement. The space complexity of an algorithm is the amount of memory it needs to run to completion. We would usually want our algorithm to take the least possible memory for operation, however in more powerful machines more resources are usually allocated for the operation in order to reduce the time taken.
- Time Complexity: It is also known as performance requirement. Time Complexity is calculated of referred in instances when we may be interested to know in advance whether the program will provide a satisfactory real time response or not. There may be several possible solutions to a problem with different time requirements or with different time complexity. Time complexity is heavily taken care of in cases when an algorithm needs to be modeled to be run on even the least powerful machines.
How to balance the two then?
The best algorithm to solve a given problem is one that requires less space in memory and takes less time to complete its execution. But in practice it is not always possible to achieve both these objectives. As we know there may be more then one approach to solve a particular problem. One approach may take more space but takes less time to complete its execution while the other approach may take less space but takes more time to complete its execution. We may have to sacrifice one at the cost of the other. If space is our constraint, then we have to choose a program that requires less space at the cost of more execution time. On the other hand if time is our constraint then we have to choose a program that takes less time to complete its execution at the cost of more space.
And with that, we finish our today's lesson. I hope you learnt something with that. Stay tuned for more and take care :)
well defined
ReplyDelete