To facilitate learning, put these together for easy viewing
I. Composition of data structure:
1. Linear structure
Linear structures are the simplest data structures, including arrays, linked lists, and the stacks, queues, and hashes derived from them.
2, trees,
Tree is a relatively complex data structure, among which the more representative is binary tree, from which derived binary heap and other data structures.
3, figure
Graphs are more complex data structures because they present many-to-many associations.
Second, time complexity
How long does it take to eat a loaf of bread n cm long, 1cm per minute?
Time complexity T(n)=O(n)
How long does it take for a loaf of bread n cm long to eat half of the rest of the loaf every minute?
T(n)=5logn time complexity T(n)=O logn
One NCM of bread and one drumstick, eat one drumstick every two minutes, then how long does it take to finish one drumstick?
Time complexity T(n)=O(1)
For a loaf of length N, it takes 1 minute to eat the first 1cm, 2 minutes to eat the second 1cm and 3 minutes to eat the third 1cm…… So how long does it take to eat the whole loaf?
T(n)=0.5n^2^+0.5n time complexity T(n)=O(n^2^)
O(n^2)>O(n)>O(logn)>O(1)
So how do you derive time complexity? The principles are as follows: ==
- If the running time is of a constant order of magnitude, it is represented by a constant 1
- Only the highest order terms in the time function are retained
- If the highest order term exists, the coefficient in front of the highest order is omitted
As computer hardware becomes more and more powerful, why do we still care so much about time complexity?
Assuming two algorithms A and B, A supercomputer can run 100 times faster than an older computer
A: T(n)=100n, time complexity O(n) running on an old computer
B: T(n)=5n^2^, time complexity O(n^2^) running on a supercomputer
| n | T(n)=100n X100 | T(n)=5n^2^ |
|---|---|---|
| 1 | 1000 | 5 |
| 5 | 5000 | 125 |
| 10 | 10, 0000 | 500 |
| 100 | 100, 0000, | 5, 0000 |
| 1000 | 1000, 0000, | 5, 0000, 0000 |
| 10000 | 10, 0000, 0000 | 500 0000 0000 |
| 100000 | 100 0000 0000 | 5, 0000, 0000, 0000 |
The answer is clear!!
Third, space complexity
Space complexity is a measure of the amount of storage space temporarily occupied by an algorithm when it is running. It is expressed as large O
//TODO
1. What is a B-tree
B-tree, also known as multi-path balanced search tree, is a very efficient data structure for organizing and maintaining external file systems
Mp.weixin.qq.com/s/rDCEFzoKH…
2. What is B+ tree
B+ trees are some variation of B- trees.
Mp.weixin.qq.com/s/jRZMMONW3…
What is a red-black tree
Mp.weixin.qq.com/s/X3zYwQXxq…