Data structure and algorithm notes

What is a data structure? What is an algorithm?

Broadly speaking, data structure refers to the storage structure of a group of data. An algorithm is a set of methods for manipulating data.

The position and way of the books in the library is the storage structure. And the way we find books is an algorithm; Like if we go by number, by category,

In a narrow sense, it refers to some well-known data structures and algorithms, such as queue, stack, heap, binary search, dynamic programming, etc. These are the crystallization of previous wisdom, we can directly use. The classical data structures and algorithms we are going to talk about are abstracted from many practical operation scenarios by our predecessors. After a lot of verification and testing, they can effectively help us solve many practical development problems.

What is the relationship between data structures and algorithms?

Data structure and algorithm are complementary. Data structures serve algorithms, which operate on specific data structures. So we can’t talk about algorithms in isolation, and we can’t talk about data structures in isolation.

The same problem can be solved by different algorithms, and the quality of one algorithm will affect the efficiency of the algorithm and even the program. The aim of algorithm analysis is to select suitable algorithm and improve algorithm. The evaluation of an algorithm is mainly analyzed from time complexity and space complexity

What is complexity analysis?

Complexity analysis is the most important concept in data structures and algorithms

Data structures and algorithms solve the problem of how to store and process data more cheaply and quickly, so we need a way to measure efficiency and resource consumption, which is called complexity analysis. If you do not learn complexity analysis, it is equivalent to knowing the operation of the formula, but not the mind.

First, the method of post-hoc statistics

  1. First, in order to evaluate the performance of the designed algorithm, it is necessary to compile corresponding programs according to the algorithm and run them in practice

  2. Time statistics depend on computer hardware, software and other environmental factors, sometimes easy to mask the advantages of the algorithm itself.

Two, the method of prior analysis and estimation (generally adopted)

Before writing the program, the algorithm is estimated according to statistical methods. The time it takes for a program written in a high-level language to run on a computer depends on the following factors:

(1) Strategies and methods adopted by the algorithm; (2). Quality of code generated by compilation; (3). Input scale of the problem; (4). Speed of machine execution.

When an algorithm is composed of control structure (sequence, branch and loop) and primitive operation (operation of inherent data type), the algorithm time depends on the combined effect of the two. To facilitate the comparison of different algorithms for the same problem, it is common practice to select an original operation that is a basic operation for the problem under study (or the type of algorithm), and take the number of repetitions of the basic operation as the time measure of the algorithm.

Data structure and algorithm itself solve the problem of fast and save; How to measure the efficiency of code execution; Time and space complexity analysis.

Continue code tomorrow: Time and space complexity analysis

reference

Blog.csdn.net/zolalad/art…

www.jianshu.com/p/f4cca5ce0…

Baike.baidu.com/item/%E7%AE…