Between data and data structure mainly has three kinds: linear structure, tree structure, graph structure, the three is also the basic structure of the data structure
1, linear structure: the structure of the one-to-one linear relationship exists between the data elements, in addition to the first and last data elements, each data element is only a precursor and a subsequent data elements
2, the tree structure: the structure of the level of the one-to-many relationship exists between the data elements, grubbing nodes, each data element is only a precursor data elements, can have zero or several subsequent data elements
3, figure structure: the structure of the data elements exist between arbitrary many-to-many relationship, each data element can have zero or several precursor data elements and zero or several subsequent data elements
Operation set algorithm (basic) : to discuss the data structure is for the purpose of implementation of the required operations on data in the computer digital on an operation, constitutes the operation of data collection, so the set operation is a very important part of the data structure,
Algorithm design depends on the logical structure of data, the realization of the algorithm depends on the physical storage structure of data,
(a) algorithm concepts and features of
Algorithm is a description of a specific problem solving steps, it is the directive finite sequence, everything must want to have the good steps in advance and then step by step, don't wrong, so is a computer to solve the problem, for some of the commonly used algorithm should memorize, such as factorial, prime Numbers, and ask whether a leap year algorithms, such as in the solution actual problem, refer to the existing similar algorithms, according to the business logic is designed in line with their own algorithms,
An algorithm should have the following five important characteristics,
(1) has a poor sexual
An algorithm should contain a finite number of steps, that is, a algorithm should be able to end after perform several steps, and each step in the limited time,
2 deterministic
Every step of the algorithm must have a precise meaning, does not produce ambiguity,
(3) the feasibility
Algorithm in each step should be to perform effectively, and get a certain result,
(4) enter
So-called input, refers to the algorithm executes, obtain the necessary data from the outside world, the computer running the program is for the purpose of data processing, in most cases, these data need by typing, in some cases, data has been included in the algorithm, the algorithm is executed don't need any data, so an algorithm can have zero or more input,
5] output
An algorithm has one or more output, this is the result of algorithm after data processing, no output of the algorithm is pointless,
Algorithm of these features can be constraints programmers write correctly algorithm, and can correct execution, to solve the problem of desired effect,
(2) algorithm design requirements
Algorithm design is good or bad about execution efficiency and algorithm design must meet the following four requirements,
(1) accuracy
Correctness means algorithm for all legal input data to be able to meet the requirements of results, in fact to verify the correctness of the algorithm is extremely difficult, because usually legal input data volume is too big, one by one by exhaustive method validation is not realistic, the so-called algorithm correctness refers to meet the test requirements,
2 readabilityAlgorithm of readability refers to a person to the difficulty of the reading comprehension of algorithm, the algorithm of readable to facilitate communication, promotes the debugging and modification of algorithm, generally increase the readability of algorithm is written when writing algorithm used by the indentation, modules such as writing method can increase the algorithm of readability,
(3) robustness,
For illegal input data, the algorithm can give the corresponding response, rather than have unpredictable consequences,
(4) low efficiency and storage requirements
Efficiency refers to the execution time of the algorithm and multiple algorithms for solving the same problem, the algorithm of short execution time of high efficiency and storage needed during the implementation of demand refers to the algorithm of maximum storage space, the smaller storage requirements of algorithm efficiency is high,
The analysis of the algorithm (3)
Solve a problem can have a variety of algorithms, so how to determine their advantages and disadvantages? A lot of standard judgment algorithm, here don't do in-depth discussions, but except for correctness must ensure that an algorithm, one of the main indicators is its efficiency,
(1) the efficiency of the algorithm measurement
Algorithm execution time is consumed by a corresponding program to run on a computer time, and time needed for the program to run on a computer is related to the following factors:
The strategy of selection algorithm itself;
(2) writing program language;
(3) to compile the code quality.
(4) machine speed to carry out the instructions;
(5) the scale of the problem,
Article (1) is the essence of the algorithm is good or bad, the first (2) (3) of article depends on the specific software support, article (4) depends on the performance of the hardware, measuring the efficiency of an algorithm should be put aside specific machine soft, hardware environment, language and writing program, compiled machine code produced by the quality, the speed of the machine executes instructions belong to software and hardware environment, so the computer hardware and software related factors aside, a program running time, only depend on the stand or fall of algorithm and the scale of the problem,
For a specific algorithm only considers the efficiency of the algorithm itself, and the execution efficiency of the algorithm itself is a function of problem size, for the same question, choose different strategies for different algorithm, different algorithms due to their respective scale function, according to these functions can compare the merits of the algorithm, the efficiency of the algorithm includes two aspects of space and time, called time complexity and space complexity respectively,
2 the time complexity of the algorithm is
An algorithm of the execution time is roughly equivalent to the sum of all of its statement execution time, the time for execution of the statement refers to the number of executions this statement and execution time needed for a product, the statement performs a specific time is needed for the actual and the speed of the machine, the quality of compiler, is closely related to the input data, and so on, has nothing to do with the stand or fall of algorithm design, so the available number the execution of the statement in the algorithm to measure the efficiency of an algorithm,
Frequency of first define algorithms in a statement, the statement refers to statements in an algorithm of frequency, the number of repeat the following offers two individual statements in the n * n order matrix multiplication algorithm and the frequency of each statement,
Statement statement frequency
for(i=0; i
C [I] [j]=0; N2
For (k=0; K
}
Algorithm all statements in the total number of executions of Tn=2 n2 n3 + 3 + 2 n + 1, which statement is the total number of executions is a function of the scale of the problem n f (n) (Tn=f (n)), further simplify, Tn available n in the expression of supreme power to measure algorithm in the order of execution time, namely the time complexity of the algorithm, do remember:
T (n)=O (f (n))
On type is ignored in Tn=f (n) the coefficient of the highest power of n items, it says the problem of size n increases, the growth rate of the execution time of the algorithm and f (n) at the same rate, called the algorithm of gradually time complexity, time complexity for short, as the time complexity of the algorithm of T (n)=O (n3),
Algorithm for all the statements in the problem of size n is the total number of executions Tn function, namely the Tn=f (n), where n is the highest power item and statement called the statement of the original operation algorithm used in frequency corresponding to the original is the realization of the basic computing algorithm operation, the original operation in the above algorithm is [I] [j] c=c [I] [j] + [I] [k] * b [k] [j], typically in one of the most original operation by deep circulation of statements,
T (n) with n increases, the slower growth, the algorithm's time complexity is lower, the following three procedures section of the original operation is given respectively count++ time complexity of three different orders of magnitude,
1) count++;
Its time complexity is O (1), is called a constant order time complexity,
(2) for (I=1; i<=n; I++)
Count++;
Its time complexity is O (n), is a linear time complexity,
(3) for (I=1; i<=n; I++)
For (j=1; J<=n; J++)
Count++;
Its time complexity is O (n2), square order time complexity,
In addition, the time complexity of algorithm can render: logarithmic order O (log2n), exponential order O (2 n),
(3) the space complexity of the algorithm is
Using the algorithm of space complexity as a measure of the required storage space, remember:
S (n)=O (f (n))
Where n is the size of the problem,
Program execution, in addition to the need to store itself the instructions, constants, variables, and the input data, also need some to manipulate data on secondary storage space,
For the input data of specific storage depends only on the problem, has nothing to do with the algorithm, so the algorithm only needs analysis in the auxiliary implementation need space unit number,
Execution times and storage cost of the algorithm is a pair of contradiction, namely the algorithm implementation of efficient often at the expense of the additional storage space, and vice versa, however, in terms of general situation, often with algorithm execution time as the main measure of algorithm,
Above part comes from the teacher by document