Complexity:
Complexity of algorithm is measured in terms of amount of time and space taken to completely execute that program or algorithm.
Time complexity :
The amount of time taken by algorithm or program to execute completely is called time complexity of that algorithm or program.
How to measure time taken by particular program or algorithm?
First we have to find more significant operations like comparisons and arithmetic operations like addition, subtraction, multiplication, division etc.
It is very hard to measure amount of time taken by particular algorithm correctly because it depends on following factors.
Ø The machine on which we are executing program.
Ø Instruction set used by machine language.
Ø The time required by each machine instruction.
Ø Compilation time i.e. time taken by compiler to convert high level language code to low level language.
These values may vary from machine to machine and we can not get exact figures. So better way to calculate time taken by each instruction to execute is the “Frequency Count“ of each statement which gets executed. That means how many times particular statement gets executed.
We will see how to calculate time complexity of a algorithm.
Algorithm 1:
|
Example :- Calculate Time complexity of the algorithm or program given below.
X = X + 1
This statement executes only once therefore the frequency count is 1.
It is denoted as O (n) i.e. O(1)
|
Algorithm 2:
|
Example : - Calculate time complexity of following code segment :
for( i =0; i<n; i++)
{
x = x +1;
}
Here,
We can calculate it’s time complexity as follows :
i) i =0 will be executed only once.
ii) I<n will executed ‘n + 1’ times.
iii) I++ will be executed ‘n’ times.
iv) X = x+ 1 will be executed ‘n’ times.
So summarize above steps
1 + (n+1) + n + n so it will give you 3n + 2
Generally, when we sum the frequency count of all the statements we get a polynomial. However, for analysis we are only interested in the order of magnitude of polynomial.
So just neglect the constant terms from the polynomial, the order of magnitude is ‘n’ and it is denoted by O(n) which is called order of n. ‘O’ is called big ‘O’ notation.
|
Space Complexity :
Ø The amount of memory taken by algorithm or program to complete its execution is called space complexity of that algorithm or program.
Ø The amount of storage space is taken is computed by considering data and their sizes.
Ø Components of space complexity are as follows:
Space Complexity = Fixed Part + Variable Part
e.g.
main()
{
Int a,b,c;
Int *ptr;
Ptr= malloc(sizeof(struct node));
}
Here,
Fixed Part :
Fixed part is not dependent on characteristics of
inputs and outputs that means as input changes
memory required for fixed part is remains same.
Change of input not effect on memory required for
fixed part. Fixed part consists of space required for simple
variables.
In above pseudo code variables a, b, c are fixed part
because it will take fixed memory and is not dependent on
change in inputs.
Variable Part:
Variable part includes a space needed by variables whose
size depends upon the particular problem being solved,
reference variables and the stack space required for
recursion.
In example , pointer variable ptr will allocate size for
structure so it depends on structure size. So memory
required for such variables may get change according to
input given.
Ø A similar notation ‘O’ is used to denote the space complexity of an algorithm.
Ø When computing for storage requirement we assume each data element needs one unit of storage space. While as the aggregate data items such as arrays will need ‘n’ units of storage space. Here ‘n’ is number of elements in an array.
Algorithm Analysis :
- Worst Case Input Analysis : - Write details given in Big ‘O’ notation
- Best case Input analysis :- Write details given in Omega notation
- Average case Input analysis : - Write details given in Theta notation.
Space Complexity = Fixed Part Component + Variable Part Component
e.g. main()
{
int a=10,b,c;
int *ptr;
ptr= malloc(sizeof(a * 2));
} Here,
Recursive algorithm :-
- Recursive algorithm uses a Divide and Conquer strategy. As per this strategy the recursive algorithm breaks down a large problem into small pieces and then applies the algorithm to each of these small pieces.
- Recursive algorithm is small, straight forward and simple to understand.
- When a function calls itself in its body then such function is called as recursive function.
- Example :
Void display()
{
display();
}
here, display function is a recursive function because it calls itself in it’s body.
Properties or characteristics of Algorithm:
Every algorithm must have following properties:
1) Input :- Algorithm must have some input.
2) Output :- Algorithm must produce desired output.
3) Finiteness :- Algorithm must terminate after finite or fixed number of
steps.
4) Definiteness :- Steps to be performed in the algorithm must be clear and
unambiguous.
5) Effectiveness :- Algorithm should be efficient (having less time and space
complexity).
Randomized Algorithms:
– Suppose you are offered the chance to participate in a TV game show.
– There are 100 boxes that you can open in an order of your choice.
– Box i contains an amount mi of money.
– This amount is unknown to you but becomes known once the box is opened.
– No two boxes contain the same amount of money. The rules of the game are very simple:
• At the beginning of the game, the presenter gives you 10 tokens.
• When you open a box and the contents of the box are larger than the contents of
all previously opened boxes, you have to hand back a token.5
• When you have to hand back a token but have no tokens, the game ends and you
lose.
• When you manage to open all of the boxes, you win and can keep all the money.
– There are strange pictures on the boxes, and the presenter gives hints by suggesting the box to be opened next.
– Your aunt, who is addicted to this show, tells you that only a few candidates win.
– Now, you ask yourself whether it is worth participating in this game.
– Is there a strategy that gives you a good chance of winning? Are the
presenter’s hints useful?
– Let us first analyze the obvious algorithm – you always follow the presenter.
– The worst case is that he makes you open the boxes in order of increasing value.
– Whenever you open a box, you have to hand back a token, and when you open the 11th box you are dead.
– The candidates and viewers would hate the presenter and he would soon be fired.
– Worst-case analysis does not give us the right information in this situation.
– The best case is that the presenter immediately tells you the best box.
– You would be happy, but there would be no time to place advertisements, so
that the presenter would again be fired.
– Best-case analysis also does not give us the right information in this situation.
– We next observe that the game is really the left-toright maxima question of the preceding section in disguise.
– You have to hand back a token whenever a new maximum shows up.
– We saw in the preceding section that the expected number of left-to-right maxima in a random permutation is Hn, the n-th harmonic number.
– For n=100, Hn <6.
– So if the presenter were to point to the boxes in random order, you would have to hand back only 6 tokens on average.
– But why should the presenter offer you the boxes in random order?
– He has no incentive to have too many winners.
– The solution is to take your fate into your own hands: open the boxes in random
– order.
– You select one of the boxes at random, open it, then choose a random box from
the remaining ones, and so on.
– How do you choose a random box? When there are k boxes left, you choose a random box by tossing a die with k sides or by choosing a random number in the range 1 to k.
– In this way, you generate a random permutation of the boxes and hence the analyse.
– On average you will have to return fewer than 6 tokens and hence your 10 tokens suffice.
– You have just seen a randomized algorithm.
No comments:
Post a Comment