May 31, 2021 Article blog
An algorithm is a step in calculating or solving a problem.
The difference is that programs are written in programming languages that computers can understand and can run on computers, while algorithms are described mathematically that humans can understand before programming. However, algorithms and programming do not have specific boundaries.
The same problem, different developer solutions are different, different programming languages, different writing methods, the purpose of setting the evaluation criteria for the algorithm is to select the optimal standard algorithm. T here are two criteria for judging the merits of an algorithm: how much space is required from running to calculating the results, and one is how long it takes to run to calculate the results. T hey are called spatial complexity and time complexity. I n general, the less complexity, the less memory is consumed, the faster it executes, and the easier it is to understand. In general, the most important thing is the running time of the algorithm.
Different algorithms, different equipment, different amount of data will lead to differences in algorithm time, through the theory calculated run time is a polynomial, and we need to be able to most intuitively understand the relationship between time and data volume changes, often ignore non-important items, get a simplest and most reflect the runtime trend of the expression, we put: ignore the non-important items, can be the most concise representation of the run time with the amount of data changes in the form of O (n), where O is capitalized, indicating that the important items are ignored. P ronunciation is the same as order; n represents the amount of data participating in the algorithm.
Why are there multiple data structures?
Depending on the purpose of use, different data types can be used to provide memory space utilization.
A list of data is one of the data structures whose data is arranged linearly, and in memory space, the data is stored in memory, each of which consists of two parts, one of the data itself and the other of a pointer that points to the next piece of storage space. When accessing data, you can only follow the pointer to one down access, until found or accessed to the end, if the amount of data in the list is n, then, find a data, the fastest need to find once, up to n times, when you need to add or delete a data in the list, only need to change one or two of the data pointers, regardless of the amount of data in the chain table, is constant level.
brief summary:
The list data is linear, the storage space is discontinuous, the time complexity of access is O(n), and the time complexity of addition and deletion is O(1).
expand:
Looping list: The data at the end of the list has no pointer, and when you add a pointer to the head data of the list for the tail data, a circular structure is formed between the list pointers, called a circular list or a ring list.
Bidirectional list: A two-way list is formed when the internal pointer of the list can point to the latter data from the previous data and from the latter element to the previous data.
Here's a note: when the definition is given, the data is made up of the data body itself and the pointer, and as the pointer increases, the storage space required for the data increases, consuming more memory. At the same time, the more pointers you have, the more complex the pointer you need to change and the more pointers you need to change.
Arrays are also one of the linearly arranged data structures, and what is different from the list is that the array's storage in memory space is continuous. W hen accessing an array, you only need to find the corresponding location based on the array index, the complexity of the lookup is constant, expressed as O(1), and when the array is increased, if the array head increases, the array needs to be expanded first. T hen move each element backward in turn, the complexity of the process is O(n), and if you add an element at the end of the array, the complexity becomes O(1), similarly, delete an element, O (1) when the tail is deleted, and O (n) when the head is deleted. As you can see, compared to the linked list, although the array is easy to query, but the operation complexity is high.
Stack is a linear data structure, when adding an element to the stack, this element is added to the top of the stack, when the element is removed, can only be read one way from the front position, and then can read the later elements, that is, the last added, but is the first to be read, so the stack is called the last-in, first-out (LIFO) mode, the way data is added and deleted is also known as the in-stack and out-of-stack. Because of the LIFO nature of the stack, it is often used to hold the latest data.
Queue is also a linear structure of the data structure, it is very similar to the stack, are one-way orderly operation, but, after first out, and the queue is like queuing, first in the front, then in the back, belong to the first-in-first-out (FIFO), to access the elements behind, can only access the previous elements, to access the target elements. Adding and removing queues is also known as joining and outing.
Hash tables store data that is combined with key value pairs, generally, the key as the identification of the data, and the value as the content of the data. Hash tables are typically used in combination with hash functions, and in the process of establishing hash tables, hash values of data need to be calculated using hash functions so that they can be quickly accessed using the characteristics of the array when accessed, and if there are multiple values at the same array location when the array is established, the same value is stored again using the linked list.
The use of hash tables speeds up array queries and has great advantages in terms of flexibility and efficiency. In programming, hash tables are often used when associating arrays.
Heap is a kind of graph, is a two-dimensional data structure, its indication can be represented by a two-bit tree chart, the data value of the child node is always larger than the parent node. I n the heap, the data at the top is always minimal, so the complexity of taking out the minimum value is always O(1) regardless of the amount of data. I n addition, because after taking out the data needs to move the last data to the top, and then compare it with the size of the child node data, while moving down, so, take out the data needs to run time and the height of the tree proportional, assuming the amount of data is n, according to the shape characteristics of the heap can be seen, the height of the tree is log2n, So the complexity of refactoring the tree is O (logn). Add data as well, add data at the end of the heap, compare its size with the parent node, and move up, knowing that the conditions for the heap are met.
If you need to take the minimum value out of the data frequently, then the heap is a good choice.
A binary tree is also called a binary search tree, or a binary sort tree. I t is a kind of two-dimensional graph structure. It is characterized by a maximum of two nodes per node, called the left subtree and the right subtree, each node on the value is greater than the value on its left subtree, the value on each node is less than the value on its right subtree.
According to these two characteristics can be seen: binary tree to find the minimum value to look for the bottom left, to find the maximum value to look for the bottom right end.
The data structure in the end which to choose according to the purpose of use to determine, the front end commonly used for the above 7 kinds.
The above is
W3Cschool编程狮
about
the front-end algorithm to get started on the "data structure"
related to the introduction, I hope to help you.
Source: www.toutiao.com/i6858491700608762380/