algorithm

Algorithm and algorithm description

algorithm:

Definition: An algorithm is a finite set of rules and is a set of operations defined to solve a specific problem.

characteristic:

  • Limitation: Normal end within a finite step, unable to form an infinite loop.
  • Certainty: Each step in the algorithm must have a definite meaning and no meaning.
  • Input: There are multiple or 0 inputs.
  • Output: At least one or more outputs.
  • Feasibility: In principle, precise operations can be performed by performing a limited number of basic operations.

Design requirements

  • Correctness of the algorithm
  • readability
  • Robustness
  • Efficient and low consumption

Algorithm Description

  • Description tools: natural language, block diagrams, high-level languages.
  • Program: is the implementation of the algorithm on the computer
    Natural language is simple but has two meanings
    The block diagram is easy to express the processing flow, and it is difficult to express the data flow.
    High-level language is accurate but too much detail

Class language

Class-like languages ​​are close to high-level languages ​​and are not strictly high-level languages. They have general specifications for high-level languages ​​and eliminate the details in the language. Focus on the algorithm processing steps themselves.

Key points

  • Master the definition and characteristics of the algorithm
  • Strive to make excellent algorithms for solving a class of problems
  • Algorithm description uses class language to highlight process ideas

Algorithm performance evaluation

Standard: Algorithm execution takes up machine resources mainly in two aspects: execution time and storage space.
Performance evaluation: The efficiency of the algorithm is related to the problem size N and should be a function of the scale of the problem.
Problem size N: reflects the nature of the problem size and has different meanings for different problems

  • The order of the matrix
  • Polynomial operation is a polynomial term
  • The figure is the fixed number
  • The set operation is the number of elements in the set

Calculation of quantitative relationships

Quantitative relationship evaluation can be presented in time and space

About the execution time of the algorithm

  • Algorithm execution time = the sum of all statement execution times
  • Statement execution time = number of executions of this statement * time required to execute once

analysis

The actual execution time of the algorithm is related to various factors such as machine hardware and system software. The essence of algorithm time comparison is the comparison of the number of executions of statements in the algorithm, which is equivalent to the time when the statement is executed once ‘1’ does not work.

Statement frequency

Statement frequency: refers to the number of times the statement is repeated in an algorithm

 Example: Multiplying two n*n matricesCorresponding statement frequency algorithm statement  n                                         for(i=0;i<n;i++)  n^2                                          for(j=0;j<n;j++)                                                  {  n^2                                                c[i][j] = 0;  n^3                                                for(k=0;k<n;k++)  n^3                                                    c[i][j] = c[i][j]+ a[i][k]*b[k][j];                                                  }

Total execution times f(n) = 2n^3 + 2n^2 + n

Time complexity of the algorithm

From the frequency of the statement, the function f(n) that increases with the size of the problem is described.
Recorded as T(n) = O(f(n))
Example: give x=x+1 the strength of the complexity analysis

  1. x=x+1 ; The time complexity is O(1), which is called constant order.
  2. For(i=1;i<n;i++) x=x+1; The time complexity is O(n), which is called linear order.
  3. For(i=1;i<n;i++){for(j=1;j<n;j++){x = x + 1;}} The time complexity is O(n^2), called the square order.

Worst time complexity

Definition: The upper bound of the execution time of the basic operation of the algorithm in the worst case.

Basic algorithm: refers to the basic arithmetic operation of the problem studied in the algorithm

Example: sequential lookup algorithm

(1) i = n - 1  (2) while(i>0; && (A[i] != k))  (3)      i--;    (4)      return i;   

analysis

Example A = [9, 10, 32, 78, 50]
Find success:

  • Worst case: The first element in A is K (case 9) and the frequency of statement (3) is n.
  • Best case: The last element in A is K (example 50) and the frequency of statement (3) is 1.

Find failure
All elements are not found (example 5) and the number of lookups is n+1.
The worst-case complexity of the algorithm is O(n).

Spatial complexity of the algorithm

The function f(n) is increased by the number of storage units, and the storage space metric is recorded as:
S(n) = O(f(n))
The complexity of the space complexity principle is not detailed in detail.

Summary and improvement

  • Master the way data is organized
  • Master the basic technology for data processing
  • Master the basic skills of algorithm design analysis

Basic concept of data structure

It includes three parts: logical structure of data, storage structure, and operation set.

Logical structure of data

  • Linear structure (1 : 1 , linear table, stack, queue, string, array, generalized table, etc.)
  • Nonlinear structure (tree 1:m, graph m: n)

Data storage structure

  • Sequential storage (a set of consecutive configuration units)
  • Non-sequential storage (a set of arbitrary configuration units)

Define the set of operations on it

Master four types of logical structure, two types of storage structure, and master the data organization method for the problem.

Pay attention to the difference between logical structure and storage structure

  • Logical structure defines the logical relationship between data elements
  • A storage structure is an implementation of a logical structure in a computer.

A logical structure can be stored in a computer using different storage methods, but must reflect the required logical relationship.

Algorithm and algorithm analysis

Focus on the definition and characteristics of the algorithm, the correctness of the algorithm, and the evaluation method of the algorithm.