1. Basic Concepts

1. Data

Data is the symbolic representation of objective things, and is the general name of all the symbols that can be input into the computer and processed by the computer program. For example: text, image, video, etc.

2. Data elements

A Data Element is a basic unit of Data, which is usually considered and processed as a unit in a computer. Equivalent to the concept of a table in a database, such as the student table needs to have information such as student number, name, class, age, etc. as a record of a person studying at a school.

3. The data items

A Data Item is an indivisible and smallest unit that constitutes a Data element. For example, the student number, name, gender and so on in the student basic information table are all data items. As above: the student’s middle school number, name, class and age are all atomic.

4. Data objects

A Data Object is a collection of Data elements with the same nature, and is a subset of Data. It is a collection of data elements, called data objects. Pasting blocks outside Docs is not supported

Second, data structure

A Data Structure is a collection of Data elements that have one or more specific relationships with each other. In other words, a data structure is a collection of data elements with a “structure”, which is the relationship that exists between data elements.

1. Logical structure

The logical structure of data describes data from the logical relationship. It has nothing to do with data storage and is independent of computer. A logical structure describes the logical relationships between data elements.

  • There is no relationship between collection structure data elements other than a “belong to the same collection” relationship. For example, to determine whether a student is a member of a class, simply think of the class as a collection structure.
  • Linear structure

There is a one-to-one relationship between data elements. For example, arranging student information data in the order in which they were enrolled would form a linear structure.

  • Tree structure

There is a one-to-many relationship between data elements. For example, in the class management system, the monitor manages multiple team leaders, and each team leader manages multiple team members, thus forming a tree structure.

  • The graph structure

Data elements have a many-to-many relationship. For example, friends between multiple students, any two students can be friends, thus forming a graph or network structure. Pasting blocks outside Docs is not supported

2. Storage structure (physical structure)

Data objects stored in a computer represent storage structures called data, also known as physical structures. It is required to store not only the data of each data element, but also the logical relationship between the data elements. The data elements are represented by a node in the computer. There are two basic storage structures for data elements in computers, namely sequential storage structure and chain storage structure. Sequential storage of structural logical relations: the logical relations between elements are represented by the relative position of each data element. Storage of elements: All elements are required to be stored in a contiguous contiguous space.

Chained storage structure logical relationship: by pointing to the next node storage address. Storage elements: Do not store sequentially but store the storage addresses of subsequent nodes.

Data types and abstract data types

2. Abstract data types

Four, algorithm

1, the algorithm

  • What is an algorithm

A finite sequence of operations specified to solve a class of problem.

  • Need to meet the conditions
    • Have a poor sexual
    • deterministic
    • The feasibility of
    • The input
    • The output
  • Advantages and disadvantages of the algorithm
    • correctness
    • readability
    • Robustness,
    • High efficiency

2. Time complexity

Ex ante analysis estimation method

  • Problem size

The problem size is the amount of input of the algorithm to solve the problem, is the essence of the problem size, generally expressed by an integer N. Problem scale N Meaning of different problems The execution time of an algorithm is roughly equal to the sum of the execution time of all statements. Execution time of a statement = number of repeated executions of the statement * Time required for one execution.

  • Statement frequency

The number of times a statement is repeated is called the Frequency Count.

  • Algorithm execution time

Suppose that the time required for each statement to execute once is unit time, then the execution time of an algorithm can be measured by the sum of the frequency of all statements in the algorithm.

Time complexity

The work of the algorithm is measured by the number of “base statements” (statements in the algorithm whose number of repeated executions is proportional to the algorithm’s execution time) executed in the algorithm. In the example above, f(n) = 2n^3+3n^2+2n+1 For n-> infinity, f(n) = n^3. Order of magnitude is denoted by O, let’s call it T(n)=O(f(n))=O(n3). Therefore, the complexity of the algorithm can be written as: T(n) = O(n3) Basic method of analyzing time complexity Find out the statement with the largest statement frequency among all statements as the basic statement, calculate the frequency of the basic statement to get a function f(n) of the problem size N, and use the symbol “O” to represent it

  • Theorem 1.1
    • If f (n) = amn ^ m + anm – 1 +… +a1n+a0 is a polynomial of degree m, then T(n)=O(n^m).

When calculating the time complexity of the algorithm, we can ignore all the coefficients of the lower power and the highest power, which can simplify the analysis of the algorithm and also reflect the meaning of the growth rate.

Case 1: Time complexity

1. Constant order

public void demo(){
    x++;
    s = 0;
}
Copy the code
T(n) = O(1)
Copy the code

2. Linear order

public void demo(){ for(int i = 0 ; i < 10000 ; i++){ x++; s = 0; }}Copy the code
T(n) = O(1)
Copy the code

3. The square order

In the following code, there are two frequencies one n and one n^2. So the most frequent statements are statements in 8 lines, time O(n^2).

public void demo(){ for(int i = 0 ; i < n; i++){ y++; } for(int i = 0 ; i < n; i++){ for(int j = 0; j < i ; j++){ x++; s = 0; }}}Copy the code
T(n) = O(n^2)
Copy the code

4. The cubic order

for(int i = 0 ; i < n; i++){
    for(int j = 0; j < i ; j++){
        for(int x = 0; x < j ; x++){
            x++;
        }
    }
}

T(n) = O(n^3)
Copy the code

5. The logarithmic order

for(int x = 0; x < n ; x*2){
    x++;
}
Copy the code
T(n) = O(log2N)
Copy the code

4. Spatial complexity

Space Complexity, a measure of the storage Space required by an algorithm, is also a function of the problem size N, denoted as:

S(n)=O(f (n))
Copy the code

Case 2. Description of space complexity

for(int i = 0; i < n/2 ; i++){
    t = a[i];
    a[i] = a[a - i -1];
    a[n - i - 1] = t;
}
Copy the code

Another variable t is needed, which has nothing to do with the problem size n, so its spatial complexity is O(1). S(n)=O(1)

for(i = 0 ; i < n ; i ++){
    b[i] = a[a - i -1];
}

for(i = 0 ; i < n ; i ++){
    a[i] = b[i];
}
Copy the code

We need another auxiliary array B of size N, so the space complexity is O(n). S(n)=O(n)