Content
The need to analyze the algorithm
Execution time of the program
Rate of increase in complexity and algorithms
The calculation algorithm complexity
Recursive equation solver

Update Date 28/05/2014 – Fix the spelling and formulas presented in a more visible.
There are many issues surrounding the algorithm, particularly complex algorithms. This article will put the issue, presents the concepts involved and the complexity of checking algorithms.
Article referenced in curriculum analysis algorithm - CTU

You. NECESSITY OF ANALYSIS ALGORITHM

While solving a problem we can have a number of different algorithms, the problem is the need to evaluate the algorithms which to choose a good algorithm (The most). Normally, we will be based on the following criteria:
1. The algorithm correctly.
2. Simple Algorithm.
3. The algorithm implemented quickly.

With request (1), to check the correctness of the algorithm we can install it and algorithms for implementation on a number of data samples and the results obtained are compared with known results. Actually, not sure how to do this because the algorithm can correctly with all the data we have tried but wrong for a certain data. And the only way to do this discovery algorithm proved wrong but is not it true. The correctness of the algorithm must be proved by mathematical. Of course this is not simple, and so we will not mention here.
When we write a program to use a few times, ê y u need (2) is the most important. We need an algorithm easy to write a program to quickly get results, duration of the program is not promoting the program anyway because they are only used a few times only.
But when a program is used many times, it requires time-saving program implementation is very important especially for those programs that need to perform data entry requirements so big (3) will be considered carefully. I call it the effective execution time of the algorithm.

II. PERIOD OF PROGRAM

A method to determine effective execution time of an algorithm is programmed it and measure the execution time of operation on a computer to determine the set of selected input. Execution time depends not only on the algorithm, but also depending on the set of computer instructions, quality of the computer and the stuff of programming. The execution can adjust to make good on a special set of data to be selected. To overcome this obstacle, Computer scientists have accepted the complexity of the access time as a basic measure of the performance of the algorithm. The term effectiveness will mention this measurement and especially for the time complexity in the worst case.
Duration of the program.
Time to make a program that is a function of the input size, symbol T(n) where n is the size (magnitude) of data on. The sum of n numbers is the execution time T(n) = Cn where c is a constant. Duration of the program is a non-negative function, ie T(n) ≥ 0 all n ≥ 0.
Unit of measure execution time.
Unit of T(n) is not a unit of measurement of time as usual hours, moments… which is usually determined by the number of commands to be executed in an ideal computer. When we say the execution time of a program is T(n) = Cn, it means that he needs Cn program execution directives.
Execution time in the worst case.
In general, the duration of the program depends not only on size, but also depends on the nature of the data in. That is, the data on the same size but the duration of the program may vary. Such programs integers arranged in ascending, when we entered the orderly sequence execution time other than when we entered no sequence order, or when we have entered an ascending sequence, the execution time is different than when we were there for a sequence in descending order. So often we see T(n) the duration of the program in the worst case on the input size n, ie: T(n) is the greatest time to implement the program for all data in the same size n.

III. RATE INCREASE AND COMPLEXITY OF ALGORITHM

Rate increases
We say that a non-negative function T(n) margin increased (growth rate) f(n) if
We can prove that For a non-negative function T(n) any, I always find the rate of increase of f(n) its.
Suppose and general: .
Place then for every n ≥1 we easily prove that:
, ie the rate of increase of .
Rate of increase of the function .
Indeed, give It is easy to prove that
The concept of the complexity of the algorithm
Suppose we have two P1 and P2 with the algorithm execution time respectively:

The algorithm will perform faster? The answer depends on the size of data on. With n < 20 the faster P1 P2 (T2<T1), by the coefficient of less than 5n ^ 3 ^ 2 coefficient of 100n (5<100). But when n > 20 on the other hand by the exponent of 100n ^ 2 smaller exponent of 5n ^ 3 (2<3). Here we are only interested in the case n>20 because when n<20 the execution time of both P1 and P2 are not large and the difference between T1 and T2 is negligible.
So logically we consider the growth rate is a function of the duration of the program itself rather than at execution time.
For a function T(n), T(n) called complexity f(n) if (ie T(n) margin increase was f(n)) and denoted by O(f(n)). (“plots of f(n)”)
with growth rate is n ^ 2 should
Attention: The(C.f(n))= O(f(n)) and C is a constant. Special O(C) = O(1)

In other words the computational complexity of the algorithm is a function of the function block on time. Because of the constant C in the function block's death on no sense, so we can ignore so complex function represents the common form after:
.
The last three functions is called exponential form, another function called polynomial. A real-time algorithm that complexity is a polynomial, then that is acceptable can be installed to perform, while the algorithm has exponential complexity, they must find ways to improve the algorithm.
Attention: in logn do not care because its base (Rule drop coefficient will mention later)
When it comes to the complexity of the algorithm is that we want to speak to the effectiveness of the execution time of the program so we can determine whether the execution time of the program is to define the complexity of the algorithm.

IV. HOW THE COMPLEXITY ALGORITHM

The calculation complexity of any algorithm is not a simple matter. But we can follow some principles:
Rules give constant
If program P segment duration T(n) = O(c1.f(n)) with c1 is a positive constant
it may consider a program segment that has the computational complexity is O(f(n)).
Communist Rule – get max
If T1(n) and T2(n) the execution time of two segments P1 and P2 program; and T1(n)= O(f(n)), T2(n)= O(g(n)) the duration of the second stage of the program after another is T(n)= O(max(f(n),g(n)))
CEO:
Assignation x:= 15 takes a constant time or O(1), Read data command readln(x) a constant time-consuming or O(1).
So time to do both commands in sequence is O(max(1,1))= O(1)
Cam's
If T1(n) and T2(n) the execution time of two program segments P1va P2 and T1(n) = O(f(n)), T2(n) = O(g(n)) the duration of the second stage of the program segment that is nested T(n) = O(f(n).g(n))
General rules to analyze a program
– Execution time of each assignation, READ, WRITE là O(1).
– Execution time of a sequence of commands is determined by the rules of public. So this time is the time to implement a particular command in the command string longest.
– Execution time is the time structure IF largest execute the following command after THEN or ELSE and check the conditions of time. Often time is O test conditions(1).
– Loop execution time is the sum (on all iterations) duration of the loop body. If the duration of the loop body does not change the duration of the loop is the product of the number of iterations to perform time loop body.
CEO: Calculate the duration of the procedure arrangement "foamy"

procedure Bubble (var a: array[1..n] of integer);
var i,j,temp: integer;
begin
	for i:=1 to n-1 do					{1}
		for j:=n downto i+1 do				{2}
			if a[j-1]>a[j] then			{3}
			begin
				temp:=a[j-1];			{4}
				a[j-1]:=a[j];			{5}
				a[j]:=temp; 			{6}
			end;
end;

On the bubble sort algorithm, we will discuss in more detail the 2. Here is, we are only interested in the complexity of the algorithm.
I found the entire program consists of a repeat order {1}, cage in order {1} command {2}, cage in order {2} command {3} and integrated in order {3} was 3 sequential order {4}, {5} and {6}. We will conduct complex calculation in order from the inside out.
First, all three assignation {4}, {5} and {6} Each takes O(1) time, comparing a[j-1] > the[j] also takes O(1) time, therefore command {3} takes O(1) time. Loop {2} perform (n-i) time, each O(1) so the loop {2} takes O((n-i).1) = O(n-i).Loop {1} repeat with i running from 1 up to n-1 execution time of the loop {1} and also the complexity of the algorithm is:

Attention: In the case of the loop can not be determined number of iterations, we must take the number of iterations in the worst case.
Search sequential. The Search function receives an array with n integers a and an integer x, function returns the logical value TRUE if an element exists a[in] = x, reverse function returns FALSE.
Search algorithm is sequential turn compare x with the elements of the array a, starting from a[1], if exists a[in] = X, then stops and returns TRUE, vice versa if all other elements of a feature, it returns FALSE X.

FUNCTION Search(a:ARRAY[1..n] OF Integer;x:Integer):Boolean;
VAR i:Integer;
	Found:Boolean;
BEGIN
	i:=1; 											{1}
	Found:=FALSE; 									{2}
	WHILE(i<=n) AND (not Found) DO					{3}
		IF A[i]=X THEN Found:=TRUE ELSE i:=i+1; 	{4}
	Search:=Found; 									{5}
END;

I see the command {1}, {2}, {3} and {5} contexture, thus the complexity of the Search function is the most complex 4 This command. Easy to see that the three orders {1}, {2} and {5} has complexity O(1) thus the complexity of the Search function is the complexity of command {3}. Cage in order {3} command {4}. Order {4} complexity O(1). In the worst case (all its elements are a different x) the loop {3} performed n times, So we have T(n) = O(n).
The complexity of the program can call the subroutine is not recursive
If we have a program with no recursive subroutine, to calculate the execution time of the program, we first calculate the execution time of the program do not call other subroutines. Then we calculate the execution time of the program you just call the subroutine that their execution time is calculated. We continue the process of evaluating the execution time of each subroutine after the execution time of all subroutines that call was evaluated. Finally we calculate the time for the main program.
Suppose we have a system of programs called together in the following diagram:

A second program called subroutine is B and C, B program subroutine is called two B1 and B2, B1 program subroutine is called two B11 and B12.
To calculate the execution time of A, It is calculated according to the following steps:
1. Calculate the duration of C, B2, B11 and B12. Because the program does not call the subroutine at all.
2. Calculate the duration of the B1. Since B1 and B12 B11 call that the execution time of B11 and B12 have been calculated in step 1.
3. Calculate the time taken by B. B1 and B2 B called because the execution time of B1 was calculated in step 2 and duration of B2 was calculated in step 1.
4. Calculate the duration of a. A call B and C because the duration of B was calculated in step 3 and duration of C has been calculated in step 1.
We can rewrite the bubble sort program as follows: First we write a procedure to perform Swap Swap two elements to each other, then the procedure Bubble, when necessary we will call this procedure Swap.

procedure Swap (var x, y: integer);
var temp: integer;
begin
	temp := x;
	x := y;
	y := temp;
end;
procedure Bubble (var a: array[1..n] of integer);
var i,j :integer;
begin
	for i:=1 to n-1 do								{1}
		for j:=n downto i+1 do						{2}
			if a[j-1]>a[j] then
				Swap(a[j-1], a[j]);					{3}
end;

In writing on, Bubble program called subroutine Swap, thus to calculate the execution time of the Bubble, we first need to calculate the execution time of the Swap. Easy to see the execution time of the O Swap(1) because it only includes 3 assignation. In the Bubble, command {3} Swap should call costs only O(1), command {2} implementation of n-i times, each takes O(1) should cost O(n-i). Order {1} implementing n-1 should:

Analysis of recursive programs
With the program can call the subroutine recursive, You can not just apply the calculation as presented because a recursive program will call itself, and if the method that is, to calculate the execution time of the program A, we must calculate the execution time of a program and a vicious cycle that can not be ended.
With recursive programs, we should first establish the recursive equation, then the recursive equation, recursive equation will be the execution time of recursive programs.
Established recursive equation
Recursive equation is an equation represented the relationship between T(n) and T(to), where T(n) the duration of the program with input size n, T(to) time implementation of the program with the input data size is k, with k < n. To establish recursive equation, It must be based on recursive programs. Normally a recursive program to solve the problem size n, must have at least one case stops with a specific n recursive calls to solve the problem size k (k0 program must be called recursively Giai_thua(A-1), This takes the recursive call T(A-1), after the result of the recursive call, programs must multiply the result with n and assign Giai_thua. Time to perform multiplication and assignment is a constant C2. So we have

This is a recursive equation to calculate the execution time of recursive programs Giai_thua.
We consider the procedure mergesort an outline as follows:

FUNCTION MergeSort (L:List; n:Integer):List;
VAR L1,L2:List;
BEGIN
	IF n=1 THEN RETURN(L)
	ELSE
	BEGIN
		Chia đôi L thành L1 và L2, với độ dài n/2;
		RETURN(Merge(MergeSort(L1,n/2),MergeSort(L2,n/2)));
	END;
END;  

For example, to sort the list L consists of 8 element 7, 4, 8, 9, 3, 1, 6, 2 we have models of mergesort illustrated as follows:

Mergesort function receives a list of length n and returns a sorted list. Merge procedure takes two lists L1 and L2 are going to list each of length n / 2 mix them together to get a list of n elements of order. Merge algorithm details we will discuss later, We only note that the time to merge the lists of length n / 2 is O(n). Call T(n) the time taken mergesort a list of n elements, then T(n/2) the duration of a list mergesort n / 2 elements. When the length L 1 (n = 1) the program is only one thing to do is return(The), it takes O(1) = C1 time. In the case of n > 1, program to perform recursive call MerSort L1 and L2 twice the length n / 2 so time to call twice recursion is 2T(n/2). Also it takes time for the division of the list L into two halves by mixing the two together and the result list (Go). It is defined to be the time to split and merge list is O(n) = C2n. So we have the following recursive equation:

The. Recursive equation solver

Methods to retrieve:
Using recursion to replace any T(m) with m<n on the right side of the PT until m = 1.
CEO: Recursive equation solver:

I have:



= …

League history and at the end we have i = j.

There:

General method
Divide the problem into a problem child and each problem size n / b. And every such share until the problem is small enough to solve (recursive). And after using this method it has been shown that for recursive equation:

I have:
T(n) = C1 if n = 1
With n>1 we have:
$latex T(n) = begin{cases} The(n) & \text{ if } the < b \\ O(n.log(n)) & \text{ if } a=b \\ O(n^{loga}) & \text{ if } a > b end{cases}$

Article referenced in curriculum analysis algorithm – CTU