Shulou(Shulou.com)06/03 Report--

This article mainly explains "basic concepts of data structure and algorithm understanding," interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let Xiaobian take you to learn "basic concepts of data structure and algorithm understanding"!

preface

Data structure and algorithm is one of the important standards embodied in programmer's internal skills, and data structure is also applied in all aspects. There is an equation of program = data structure + algorithm in the industry. Middleware developers and architects are working hard to optimize middleware, project structure, and algorithms to improve operational efficiency and reduce memory footprint, where data structure plays a very important role. In addition, the data structure also contains some object-oriented ideas, so learning to master the data structure greatly improves the abstract ability of logical thinking.

Why learn data structures and algorithms? If you are still a student, then this course is compulsory, and the entrance exam is basically a compulsory subject. The data structure and algorithm are also very important inspection points necessary for interviews and written examinations. If the work of the data structure and algorithm is also a very important manifestation of internal improvement, for programmers, want to get satisfactory results, data structure and algorithm is a necessary skill!

data structure

concept

A data structure is the way a computer stores and organizes data. A data structure is a collection of data elements that have one or more specific relationships with each other. Often, a well-chosen data structure can lead to higher operational or storage efficiencies.

In short, data structure is a series of storage structures according to certain execution rules, with a certain execution algorithm formed by efficient storage structure. Relational databases, non-relational databases, search engine storage, message queues, etc., as we know them, are good uses of large data structures. Of course, these application middleware should not only consider the pure structure problem. Other factors such as actual os, network, etc. are also considered.

And for data structures and algorithms this column. The first thing we programmers change is the abstract data structure that runs in memory. Is a relatively single type of data structure, such as linear structure, tree, graph, etc.

related terms

In the data structure and algorithm, many people are confused about the relationship between data, data objects, data elements and data items. Draw a picture to smooth it out, and then give an example to share with you below.

User information table users

idnamesex001bigsaiman002smallsaiman003 Vegetable Xu Kun woman

Listlist;//list of data objects

class users { //slightly int id; String name; String sex;} //list and woman are data Listlist;//data object Listwoman;//data object woman list.add (new users(001,"bigsai","man"));//add data element a user by (001, bigsai, man) Three data items make up list. add.(new users(002,"smallsai","man"));//data element list.add(new users(003,"Caixu Kun","woman"));//data element woman.add(list.get(2));//03,"Caixu Kun","woman"

Data: Symbolic representation of an objective object, a collection of symbols that can be input into a computer and processed by a computer program. The three user information records in the above table are data (there may be multiple tables and multiple sets, and there is only one). These data are usually user input or custom constructed. Of course, some images and sounds are also data.

Data elements: Data elements are the basic units of data. A data element consists of several data items! Think of it as a pojo object or a record in a database. For example, Caixu Kun's record was a data element.

Data item: The user field/attribute consists of id, name, sex, etc. These are data items. A data item is the smallest indivisible field that constitutes a data element. This can be seen as a pojo object or a value of an attribute/field of a table (people).

Data object: A collection of data elements of the same nature. is a subset of the data. For example, the users table, list collection, and woman collection above are all data objects. A single table or collection can be a data object.

In general, the data range is the widest, all data is data, and the data object is only a set with the same properties. This set is a subset of data, but it is not the basic unit of data, and the data element is the basic unit of data. For example, table cat and table dog are both data, and table cat is a data object (because both describe cat objects), but the basic unit of data is not cat and dog, but each of their specific items, such as kitten No. 1, big cat No. 2, husky No. 1, Tibetan mastiff No. 2. Each of these items is the basic unit of data.

It is easy to confuse data types and abstract data types:

data type

Atomic type: A type whose value is not divisible. int, char, double, float, etc.

Structure type: A data type whose values can be subdivided into components. For example, various structures of structural body structure, etc.

Abstract Data Type (ADT): An abstract data type (ADT) is an algorithm that implements a storage structure that includes stored data elements and implements basic operations. making it possible to study and use only its structure without considering its implementation details. For example, we use List, Map, Set, etc. only need to know its api and property functions. The specific implementation may be different schemes, for example, the implementation of List has different choices of array and linked list.

three elements

Logical structure: logical relationships between data elements. Logic structures are classified into linear structures and nonlinear structures. Linear structures are sequential lists, linked lists and the like. Nonlinearity is set, tree, graph structure.

Storage structure: the representation of data structure in computer (also known as image, also known as physical structure), storage structure is mainly divided into sequential storage, chain storage, index storage and hash (hash) storage, these storage through the following diagram to understand briefly (only for understanding do not consider more):

Operations on data: Operations applied to data include the definition and implementation of operations, the definition of operations based on logical structures, and the implementation of operations based on storage structures.

Here it is easy to confuse the concepts of logical structure and storage structure. For logical structure, it is not difficult to get logical two words, logical relationship is the relationship between the two data without considering the physical address, such as linear structure and nonlinear structure, it describes the way and form of contact in a group of data, he is aimed at data. What I like is the function of data structure. For example, linear table is ordered before and after. I need an ordered collection to use linear table.

The memory structure is linked to the physical address. Because the same logical structure uses different storage structures to achieve different scenarios and performance. For example, there are many ways to implement a linear table. For example, sequential tables and linked lists (Arraylist,Linkedlist) have different storage structures, one is sequential storage (array) implementation, and the other is chained storage (linked list) implementation. It focuses on relationships between physical locations where computers operate. However, some data structures implemented by the same type of storage structure usually have some similar common points and shortcomings (linear easy to check and difficult to insert, chain easy to insert and difficult to check, etc.).

algorithm analysis

The concepts related to data structure have been discussed above, and some concepts of algorithm analysis are described below.

Five important characteristics of algorithm: finiteness, certainty, feasibility, input and output. These can be understood literally, where finiteness emphasizes that the algorithm cannot loop indefinitely when it has an end; certainty is that each instruction has its meaning, and the same input gets the same output; feasibility refers to the algorithm that can be implemented after several executions of each step; input is 0 or more inputs (0); output is 1 or more outputs (there must be outputs).

A good algorithm usually focuses on efficiency and space resource occupation (time complexity and space complexity). Usually, complexity is more described by an order of magnitude and rarely described by specific numbers.

space complexity

Concept: is a measure of the temporary storage space occupied by an algorithm during operation, denoted as S(n)=O(f(n))

Spatial complexity is actually a relatively low proportion of the algorithm (we often use data structures and algorithms that sacrifice space for time), but the importance of spatial complexity cannot be ignored. Memory is a maximum indicator both in the brush and actual project production. This is especially true for Java. The memory itself is large, and if the storage logic used is not very good, it will occupy more system resources and cause pressure on the service.

In many cases, the algorithm sacrifices space for time (efficiency). For example, we know that string matching String.contains() method, we all know that it is brute-force cracking, time complexity is O(n^2), do not need to rely on extra memory. The KMP algorithm is inherently brute-force in terms of efficiency and speed, but KMP relies on other arrays (next[]) for label storage operations. There's space overhead. For example, merge sort will also use the new array to perform step-by-step calculation in the recursive partition, improving efficiency, but increasing the memory overhead with little impact.

Of course, the maximum space cost of the algorithm cannot exceed the maximum value set by jvm, which is generally 2G. (2147483645) If you open a two-dimensional array of multi-dimensional data, don't open it too large, it may cause heap OutOfMemoryError.

time complexity

Concept: In computer science, the time complexity of an algorithm is a function that qualitatively describes the running time of the algorithm. This is a function of the length of the string representing the input value of the algorithm. Time complexity is often expressed in large O notation, excluding the lower order terms and leading coefficients of this function. Using this approach, the time complexity can be said to be asymptotic, considering the case when the magnitude of the input approaches infinity.

O(1) < O(logn) < O(n)

Common Time Complexity: Many people have vague ideas about time complexity. Here are some examples of time complexity.

O(1): Constant function

a=15

O(logn): logarithmic function

for(int i=1;i

There are also typical binary search, extended Euclid, fast idempotent algorithms are O(logn). It is a highly efficient algorithm.

O(n): linear function

for (int i=0;i

It is common and can solve most problems well.

O(nlogn):

for (int i=1;i

Many common sorting algorithms are nlogn in normal cases, such as fast sorting and merge sorting. Most of the algorithm efficiency is also good.

O(n^2)

for(int i=0;i

O(n^2) is the most efficient solution. O(n^2) and higher orders perform poorly for large data sets.

Of course, if the same is n=10000, then the number of times and time of execution of the algorithm are different with different time complexity.

Specific n Execution times O(1)100001O(log2n)1000014O( n^1/2)10000100O(n)1000010000O(nlog2 n)10000140000O(n^2) 100001000000 O(n^3) 1000010000000

Reducing algorithm complexity depends on the characteristics and advantages of data structures, such as binary sort tree lookup, segment tree dynamic sorting, etc. These data structures solve some problems with some very good performance. O(n2), O(nlogn), O(nlogn). Getting faster requires more sophisticated data structures and more sophisticated algorithms.

Time complexity calculation Time complexity calculation General steps: 1. Find the statement with the most execution times; 2. Calculate the order of magnitude of statement execution; 3. Use O to represent the result. And there are two rules:

Addition rule: If there are multiple parallel execution statements under the same program, then take the largest one,eg:

T(n)=O(m)+O(n)=max(O(m),O(n)); T(n)=O(n)+O(nlogn)=max(O(n),O(nlogn))=O(nlogn);

Multiplication rules: cyclic structure, time complexity calculated by multiplication,eg:

T(n)=O(m)*O(n)=O(mn) T(n)=O(m)*O(m)=O(m^2)

Of course, the time complexity of many algorithms is also related to the input data, which is divided into optimal time complexity (when the number of executions is the least), worst time complexity (when the number of executions is the least), and average time complexity, which has been specifically analyzed in the sorting algorithm, but we usually use average time complexity to measure the quality of an algorithm.

Data structure and algorithm learning

After the introduction of the basic concepts of data structure and algorithm, in terms of learning data structure and algorithm, I personally write the steps of the classic data structure and algorithm learning process below, hoping to give you a reference:

data structure

Single-linked list (leading node, not leading node) design and implementation (add, delete, change), double linked list design and implementation

Stack design and implementation (arrays and linked lists), Queue design and implementation (arrays and linked lists)

Binary tree concept learning, binary tree preorder, middle order, postorder traversal recursive, non-recursive implementation, sequence traversal

Design and Implementation of Binary Sort Tree (Insert Delete)

Heap (priority queue, heap sort)

Design and Implementation of AVL(Balanced) Tree

Concept understanding of the principle of spreading tree and red-black tree

B, B+ principle concept understanding

Huffman tree principle concept understanding (greedy strategy)

Hash (hash table) principle concept understanding (several ways to resolve hash conflicts)

union lookup set/disjoint set (optimization and path compression)

graph theory topological sorting

Graph theory dfs depth-first traversal, bfs breadth-first traversal

Shortest Path Dijkstra Algorithm, Floyd Algorithm, spfa Algorithm

Minimum spanning tree prim algorithm, kruskal algorithm

Other data structures Segment trees, suffix arrays, etc.

classical algorithm

Recursive algorithms (factorial, Fibonacci, Tower of Hanoi problems)

binary search

Divide and conquer algorithm (fast sort, merge sort, find the nearest point equivalence problem)

Greedy algorithm (use more, interval selection problem, interval coverage problem)

Common dynamic programming (LCS(longest common subsequence) LIS(longest rising subsequence) knapsack problems, etc.)

Backtracking algorithm (classical eight queens problem, total permutation problem)

Bit operation FAQ (refer to Sword Finger offer and LeetCode questions)

Fast exponentiation algorithm (fast exponentiation, fast matrix exponentiation)

Kmp string matching algorithm

All other number theory algorithms (Euclid, Extended Euclid, Chinese Residue Theorem, etc.)

At this point, I believe that everyone has a deeper understanding of the "basic concepts of data structure and algorithm understanding," so let's actually operate it! Here is the website, more related content can enter the relevant channels for inquiry, pay attention to us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.