This is the 14th day of my participation in Gwen Challenge

The introduction

The steps a computer takes to solve a problem

1. Abstract an appropriate mathematical model from a specific problem 2. Design an algorithm to solve the mathematical model 3. Use computer language to write the program to implement the algorithm, debug and run the program until finally get the solution of the problemCopy the code

Problem-solving steps

Data Structure

Data structures are ways of organizing data and storing it

Data structure refers to the way in which a group of data with one or more specific relationships to each other is organized and stored in a computer, as well as the set of operations defined on this group of data.

Logical structure of data

Data and the way it is organized are called logical structures

The relationship between data structures and algorithms and programs

Program = data structure + algorithm

The data structure

Basic concepts and terminology

Data (Data)

Any object that can be stored and processed by a computer

Data Elements

Data is a set, in which each individual is an element of the set. A data element is the basic unit of data

Data Item

Data elements often also consist of several data items. It is the smallest identification unit of indivisible data.

data

Logical Structure of data

Structural relationships between data elements

Logical relation: Relation or adjacency relation between data elements

A collection of

There is no adjacency between any two points, and the organization form is loose

The collection structure

Linear structure

The nodes are arranged in a logical chain, one next to the other.

Linear structure

A tree structure

With the characteristics of branches and hierarchies, the upper node can be adjacent to multiple lower nodes, but the lower node can only be adjacent to one of the upper nodes.

A tree structure

The graph structure

Most complicated, any two nodes can be joined next to each other

Graph structure

Storage Structure/Physical Structure of data

The implementation of the logical structure of data in a computer is called the storage structure of data (physical structure)

Storage of data structures = storage of data elements + storage of logical relations

Sequential structure

Sequential storage: The logical relationship of data is represented by the relative storage location of data elements

Method: Store all storage nodes into a contiguous storage area

The characteristics of

1. Allocate the length in advance, and estimate the storage capacity required for storing data. 2. Access fast, is a random access structureCopy the code

The chain structure

Chained storage: the logical relationship of data is represented by Pointers to the addresses of data elements

The storage unit of storage nodes are divided into two parts: data items | pointer

The characteristics of

1. Dynamic allocation, without pre-determined memory allocation 2. Insert and delete without moving other elements 3. Non-random access architectureCopy the code

Index storage

Index storage: the index in the index table indicates the storage location of each storage node

Hash storage mode

Hash storage: Use hash function to indicate the storage location of each node

operation

Refers to the operation imposed on a logical structure, that is, the processing of the logical structure

Processing operation

Its operation changes the value of the original logical structure. Such as: node number, node content and so on.

Referential operation

Its operation does not change the value of the original logical structure.

Basic operation

1. Create 2. Search 3Copy the code

Algorithm and Description

The algorithm specifies all the processing steps and execution sequence required to solve a given type of problem, so that the given type of problem can be solved in a finite time

An algorithm is a description of the steps to solve a particular problem. It is a finite sequence of instructions.

features

1. Fineness: an algorithm always ends after a finite step is performed. 2. Determinism: Each step of the algorithm must be clearly defined. Feasibility: Each step in the algorithm can be accomplished by already realized operation 4. Input: An algorithm has zero or more inputs from a specific set of objects 5. Outputs: An algorithm has one or more outputs, which are quantities that have a specific relationship to the inputsCopy the code

Algorithm analysis

The design of the algorithm should satisfy

  1. Correctness: Produces an acceptable output from a valid input
  2. Legibility: The algorithm should be easy to read and communicate, which is also the premise to ensure the correctness of the algorithm (e.g., adding comments).
  3. Robustness: The algorithm can also react appropriately without crashing when invalid data is entered. For example, error information is displayed. Proper error handling should be considered in the algorithm.
  4. Space-time: refers to the time and space complexity of an algorithm. Algorithm analysis mainly analyzes the time and space complexity of an algorithm to improve the efficiency of the algorithm

Time complexity

The total number of steps an algorithm takes to run, usually as a function of the size of the problem

Determine the computation amount of the algorithm

Reasonably choose one or more operations as standard operations

By default, the assignment statement is the standard operation.

Determine the total number of standard operations performed by each algorithm and specify this number as the amount of computation for the algorithm

Worst-case time complexity of the algorithm

The computation of the algorithm is the maximum computation of the algorithm under all inputs

Average case time complexity of the algorithm

The calculated amount of the algorithm is taken as the weighted average of the calculated amount of the algorithm under all inputs

Asymptotic time complexity

T(n) = O(f(n))

F (n) is some function of problem size n

The big O notation is also called the asymptotic notation

T(n) is called the asymptotic time complexity of the algorithm, or time complexity for short

The common time complexity is ordered by order of magnitude

O(1) < O(log2(n)) < O(n) < O(nlog2(n)) < O(n^2) < O(n^c) < O(2^n)

Constant order < logarithmic order < linear order < linear logarithmic order < square order < polynomial order < exponential order

It is generally believed that:

Constant order O(1), the time complexity of the algorithm has nothing to do with the input size N

Algorithms with exponential order are practically uncomputable

Algorithms whose order is less than square are efficient

Spatial complexity

S(n) = O(g(n))

G (n) is some function of problem size n

The amount of storage an algorithm takes up while executing, usually as a function of the problem size

It is a measure of the storage space temporarily occupied by an algorithm while it is running.

The amount of storage required by an algorithm during its execution includes the following

Space occupied by program code 2. Space occupied by input data 3. Space occupied by auxiliary variablesCopy the code

When estimating spatial complexity, we usually only analyze the space occupied by auxiliary variables