Algorithm
Download 51.62 Kb.
|
- Navigate this page:
- Properities of the Algorithm
- Computational Complexity
- Complexity analysis
- Space Efficiency
- Time Efficiency
- Characteristics
- Worst-case, Best-case and Average-case Efficiencies
| Complexity Analysis
Algorithm: An Algorithm is a mechanism to manipulate data in data structure. 1. It is a step-by-step method of solving a problem or making decisions, as in making a diagnosis. 2. An established mechanical procedure for solving certain mathematical problems. An algorithm is just the outline or idea behind a program. We express algorithms in pseudo-code: something resembling C or C++, but with some statements in English rather than within the programming language. It is expected that one could translate each pseudo-code statement to a small number of lines of actual code, easily and mechanically. Properities of the Algorithm: 1) Finiteness: - an algorithm terminates after a finite numbers of steps. 2) Definiteness: - each step in algorithm is unambiguous. This means that the action specified by the step cannot be interpreted (explain the meaning of) in multiple ways & can be performed without any confusion. 3) Input:- an algorithm accepts zero or more inputs 4) Output:- it produces at least one output. 5) Effectiveness:- it consists of basic instructions that are realizable. This means that the instructions can be performed by using the given inputs in a finite amount of time Computational Complexity To compare the efficiency of algorithms, a measure of the degree of difficulty of an algorithm called Computational Complexity is developed. Complexity analysis Efficiency of an algorithm: the task of determine the computing time and storage space required of an algorithm is known as efficiency of an algorithm or performance analysis. Two kind of efficiency: Space efficiency. Time efficiency. Space Efficiency: The amount of temporary required for running the algorithm, it has two components. Fixed static part: space for numbers, constants size of input and output Cp Fixed static part. Variable dynamic part: variables whose size is dependent problem, Sp space required for variable dynamic part. A total space requirement for an algorithm is the sum of both fixed and dynamic part. S(P)= CP+SP Example 1: Find sum of two integer numbers. int x,y,sum; sum = x+y; In this code no variable dynamic part space for each integer variable is 4 byte. We have 3 integer variable and space needed for x,y and sum = 12 bytes. S(P)= CP+SP S(P)= 12 + 0 = 12 Example 2: Find sum of array elements. int add(int x[], int n) { int total = 0, i; for(i=0; i return total; } S(P)= CP+SP S(P)= 4 X 4 + n = 16 + n Time Efficiency: the amount of time to run the program is known as time efficiency or time complexity. Total time taken by an algorithm is the sum of compile time and runtime.
Example 3: for( i=0; i 1 unit of time. Big O: Big O is a technique for comparing two or more algorithm. Characteristics: Comparison of algorithms without hardware consideration. Simplification of equation of ease comparison.
Worst-case, Best-case and Average-case Efficiencies: Let us the complexity function T(n) for certain cases. Worst case: It gives the maximum value of T(n) for any possible input. Best case: It gives the minimum value of T(n) for any possible input. Average case: It gives the expected value of T(n) Page of Directory: 2013 2013 -> Annual InStructional unit plan 2013 -> The Ministry of Education and Science of Ukraine 2013 -> #1 a lifesafer of virginia inc 2013 -> Name(s): your name here team or Group #(if applicable): Professor’s name 2013 -> Alcott Local School Council (lcs) Meeting Minutes 2013 -> Table Of Contents introduction 2 2013 -> Supplemental demographic information 2013 -> 【Education&Working Experience】 Download 51.62 Kb. Share with your friends:
|
