1.3 Algorithm and Algorithm Analysis Algorithms and Algorithm Analysis 1.3.1 Algorithms The so-called algorithm is a description of the problem solving step, which is a limited sequence of instructions, where each instruction represents one or more operations. In CLRS, it is the definition of algorithm: Informally, An Algorithm is any Well-Defined Computational Procedure That Takes Some Value, OR Set of Values, AS Input and Products Some Value, Or Set of Values, As Output. An Algorithm IS thus a sequence of computational steuts That Transform The Input Input INTO The OUTPUT.
An algorithm must meet the following five important features:
1. Paste For any set of legal input values, it will end after performing poor steps, ie each step in the algorithm can be completed within a limited time;
2. Determination For the operations that should be performed in each case, there are exact provisions in the algorithm that make the executor or readers of the algorithm and how to perform it. And under any conditions, the algorithm has only one execution path;
3. The operations described in the feasibility algorithm can be implemented limited to the basic operation operations that have been implemented;
4. There is an input as an algorithm machining object, which is usually embodied as a set of variables in the algorithm. Some inputs need to be entered during the execution of the algorithm, and some algorithm can be not input on the surface, which is actually in the embedding algorithm;
5. There is an output it is a set of values with the input has a determination relationship, which is the result obtained after the algorithm performs processing.
1.3.2 principle of algorithm design
We should strictly consider the design algorithm:
1. CORRECTNESS
First, the algorithm should be satisfied with the need for a specific "specification" manner. The understanding of the "correct" of the algorithm can have the following four levels:
a. Syntax errors in the program;
b. The program can obtain the output result that meets the requirements for several sets of input data;
C. The procedure can obtain the result of the requirements for carefully selective, typical, harsh input data.
d. The procedure can obtain the result of the requirements for all legitimate input data;
Usually the correctness of the Siki-layer significance is used as a standard for measuring whether a algorithm is qualified. Because as input, we sometimes impossible to make all expectations in advance.
2. Readability
The algorithm is mainly for people's reading and communication, followed by executing computer. Therefore, the algorithm should be easy to understand; on the other hand, the procedures that are difficult to read are easy to hide more errors and difficult to debug; some programmers always write only their own algorithms to understand, this algorithm is not Too big value.
3. RUBUSTNESS
When the input data is illegal, the algorithm should properly reflect or perform the corresponding processing, rather than generating inexplicable output results. This requires us to fully consider the unmected exception, and the method for handling an error should not be the execution of the interrupt program, but should return a value indicating an error or error in order to over higher abstract hierarchy Treatment.
4. High efficiency and low storage demand
Usually, efficiency refers to an algorithm execution time; the storage amount refers to the maximum storage space required during the execution of the algorithm. Both are related to the size of the problem.
1.3.3 Measurement Methods and Guidelines for Algorithm Efficiency Typically have two methods of measureing algorithm efficiency:
1. Post-final statistics
Disadvantages:
(1) The program must be executed to determine
(2) Other factors (such as hardware, software environment) masking algorithm
2. Pre-analysis estimation method
Mainly to consume time. And an algorithm implementation time-related factor:
1. Strategy for algorithm
2. Size
3. Write the language
4. The quality of machine code generated by the compiler
5. The speed of the computer execution instruction
The size of the "running workload" of a particular algorithm only relies on the scale of the problem (usually using an integer N), or, it is a function of the problem scale. If the problem N increases, the growth rate of the algorithm is the same as the growth rate of the algorithm, and the growth rate of f (n) is the same.
T (n) = O (f (n))
T (N) is the Asymptotic Time Complexity, referred to as time complexity. O is an order of order symbols.
Below we discuss how to estimate the time complexity of the algorithm
Algorithm = Control Structure Original Action (Operation of Inherent Data Types)
Algorithm execution time = execution time of the original operation (i) × the original operation (i) execution time
The sum of the execution time of the algorithm and the number of procedures execution times
Let's introduce a concept:
For (j = 1; j <= n; j) for (k = 1; k <= n; k) { x; x = x;}
The number of statements repeatedly executed by the statement is called the statement of the Frequency Count x statement is N2.
We often use: From the algorithm to the original operation of the basic operation, the number of times the basic operation is repeated in the algorithm as a measure of the algorithm runtime. In most cases, most of the cases are the original operation in the statement in the deepest loop.
E.g:
For (i = 1; i <= n; i) for (j = 1; j <= n; J) {C [i, j] = 0; for (k = 1; k <= n ; k) C [i, j] = a [i, k] * b [k, j];}
The basic operation of this algorithm is multiplication. Time complexity is O (N3)
1.3.4 Algorithm's memory space for algorithms
The spatial complexity of the algorithm s (n) = O (g (n))
It is shown that as the scale N increases, the growth rate of the algorithm runs is the same as the growth rate of G (n).
The amount of memory of the algorithm includes:
1. Enter the space occupied by the data;
2. The program itself is spaced;
3. Auxiliary variable space.
If the space occupied by the input data is only dependent on the problem itself, and the algorithm has nothing to do, it is only necessary to analyze additional space other than the input and programs. If the required additional space is constant relative to the input data, this algorithm is called in place.
