preface
This issue is our first real study of data structures. Let's have a look~
1. Data structure and algorithm
1.1 data structure
: the way in which computers store and organize data. There is a specific relationship between these data, and at the same time, they form a set.
Simply put
Data structure is to manage data in memory.
1.2 algorithm
: process unprocessed data into processed data.
In short, algorithm is "processing".
So how to measure the quality of the algorithm?
If the same thing is handled by different people, it will have different effects; The same pile of data is handled by different algorithms with different efficiency.
To measure the quality of the algorithm, predecessors introduced the concept of complexity
2. Complexity
Processing a pile of data: it takes time to execute the code; Space is needed to implement the algorithm
So there is time complexity and space complexity
How to express complexity? Running time of computer test? Accurately observe the memory condition?
It is obviously unrealistic to have different machines running at different speeds and other disturbances. Predecessors thought of using functions to express complexity
2.1 representation of complexity
Big O notation: indicates the asymptotic behavior of a function
With it, we can not only describe the general complexity of the algorithm, but also not cumbersome
Speaking of using functions to express complexity, we have these expressions
 O( 1 )
 O( N )
 O( N^2)
 ...
These functions are also commonly called large order O
This representation is also called the large O asymptotic representation
How do you get the N in the big O function?
Look down slowly~
2.2 time complexity
: used to measure the speed of algorithm execution
Can the speed of algorithm execution be measured by time? No, the machine is different, and the speed is different. My program only ran for 3ms. Maybe it's just because I'm the equipment brother.
How to measure the speed of the algorithm?
The number of statements executed. No matter what machine, the more statements are executed, the more time it takes to execute.
therefore
The time complexity of the algorithm can only be expressed by the execution times of the basic operations in the algorithm
Let's take an example:
cnt++; How many times has this statement been executed?
int cnt = 0; void f1(int n) { int i = 0; for (i = 0; i < n; i++) { int j = 0; for (j = 0; j < n; j++) { cnt++; } } } void f2(int n) { int i = 0; for (i = 0; i < 2 * n; i++) { cnt++; } } int m = 20; void f3(int m) { while (m) { cnt++; } } int main() { f1(n); f2(n); f3(m); return 0; }
 f1(n): twolevel for loop controlled by N  n^2 times
 f2(n): one layer for loop controlled by 2*n  2*n times
 f3(m):m is 10, while m control  10 times
 Total: n^2 + 2*n + m times
So is the complexity written as O(n^2 + 2*n + m)?
We mentioned that the big O symbol means that the function is asymptotic. What is the real meaning of function asymptotic? As I understand it, N approaches infinity
:
 For n^2, 2*n is the younger brother
 There is no difference between N and 2*n
 Constant is my brother
 ...
2.2.1 derivation of large order O
In fact, this also reflects the derivation method of large O function:
 Replace all addition constants in brackets with constant 1
 Only the highest order items are reserved in brackets
 If the term of the highest order exists and is not 1, its coefficient is removed
The time complexity of the above program is expressed by the large o order, which is O(n^2)
2.2.2 common time complexity
2.2.3 worst case
In addition to big O, there is another criterion for computing time complexity:
For the algorithm, we generally pay attention to its worstcase operation; Individual algorithms will pay attention to different operation conditions according to their characteristics: average and worst
For example, Hill ranking focuses on the average, because the worst case rarely occurs
It's called expectation management when it comes to being tall, hahahaha
There is such an algorithm, the worst complexity is O(n^2), usually O(n), tell you the complexity is O(n^2)
You get the program and run, O(n), yo, pretty fast; I happen to encounter the worst case, O(n^2), "well... It's really the complexity of O(n^2)"
2.2.4 example drill
In the last few examples, calculate their time complexity
Example 1
void f1(int n) { int count = 0; for (int k = 0; k < 2 * n ; ++ k) { ++count; } int m = 10; while (m) { ++count; } printf("%d\n", count); }
 The first for loop is controlled by 2*n, and the number of executions is n^2 as n increases
 The second cycle is controlled by constant m, which is executed 10 times and constant times
 Then the time complexity of f1(int n) is O(n^2)  the constant order is brother
Example 2
void f2(int n, int m) { int count = 0; for (int k = 0; k < m; ++ k) { ++count; } for (int k = 0; k < n ; ++ k) { ++count; } printf("%d\n", count); }
 The first for loop is controlled by M. with the increase of M, it is executed m times
 The second for loop is controlled by N, which is executed n times as n increases
 Then the time complexity of f2(int n) is O(m+n)
Example 3
void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i1] > a[i]) { Swap(&a[i1], &a[i]); exchange = 1; } } if (exchange == 0) break; } }
 The first for loop is controlled by N, and the loop body is executed n times with the increase of n
 The second for loop is controlled by end. With the increase of N, the loop body executes 1+2+3+... + (n2)+(n1) times, which is an arithmetic sequence, n*(n1)*1/2, that is, n^2 times
 Then the time complexity of BubbleSort is O(n^2)  compared with the n^2 of the first layer, it is a younger brother
 *Interestingly, we added an optimization to judge whether it is orderly, so the best case of BubbleSort is O(n)  traversing the array n times
Example 3
const char * strchr ( const char * str, int character );
The function of strc is to find characters in strings

Best case: it only needs constant times to find, O(1)

Average situation: it takes n/2 times to find, O(n/2)

Worst case: it takes n times to find, O(n)

The characteristics of this algorithm are not special, and we pay attention to the worst case: the time complexity is O(n)
After practicing here, many partners may feel the law. In fact, they just look at the variables that control the cycle! n/m corresponds to O(n)/O(m); 100 corresponds to O(1)
But is it really that simple? In fact, the number of executions is not only determined by the variables that control the loop, but also involves the logic of the algorithm
Just look at the twopoint search below
Example 4
int BinarySearch(int* a, int n, int x) { assert(a); int left = 0; int right = n1; // [begin, end]: begin and end are left closed and right closed intervals, so there is a = sign while (left <= right) { int mid = left + ((rightleft)>>1); if (a[mid] < x) begin = mid+1; else if (a[mid] > x) end = mid1; else return mid; } return 1; }
The while loop is controlled by left and right. With the increase of N, the search range is constantly changing: n /2 /2 /... /2 /2, and finally the range is reduced to only one number. That is, every time you search the range /2, you end up with 1

Suppose you find x times, n /2 /2 /.... /2 /2 = 1  > n = 1*2^x = 2^x  > x=
O ( l o g 2 n ) O(log_2n) O(log2n) 
In the calculation of complexity, we often omit the base 2

Then the time complexity of the binary search algorithm is
O ( l o g n ) O(log_n) O(logn)
Example 3
const char * strchr ( const char * str, int character );
*strchr is used to find the characters in the string. Since it is a search, it can also be divided into situations
 Best case: O(1)
 Average: O(n/2)
 Worst case: O(n)
 Time complexity: O(n)
Example 4
long long Fac(size_t n) { if (1 == n) return 1; return Fac(n  1) * n;jjjjjkjjjjjjj
 n! = 1*2*3*...*n
 As n increases, the number of recursions increases, and each call executes code only a constant number of times
 Then the time complexity is O(n)
What if so?
long long Fac(size_t n) { size_t M = n; while (M) { printf("%d ", n); } if (1 == n) return 1; return Fac(n  1) * n; }
 As n increases, the number of calls increases, and the code is executed n times per call
 Then the time complexity is O(n^2)
Example 5
long long Fib(size_t n) { if (n < 3) return 1; return Fib(n  1) + Fib(n  2); }

It can be seen that the recursion number of the function is 2^0 + 2^1 +... + 2(n1), and the sum of the first n terms of the proportional sequence is 2n  1

Time complexity is O(2^n)
This complexity is too high. It's useless to give n a big point. I can't watch it anymore. Let's optimize it
//Iterative Fib long long Fib(size_t n) { if (n < 3) return 1; long long f1 = 1, f2 = 1, f3; size_t i = 0; for (i = 3; i <= n; i++) { //Find the ith Fibonacci number f3 = f1 + f2; //iteration f1 = f2; f2 = f3; } return f3; }
 Only execute the loop body n3 times
 Then the time complexity is O(n)
2.4 spatial complexity
: used to measure the space required for algorithm execution
One thing we need to know: time cannot be reused; Space can be reused
in other words
Open + release or apply + destroy = = no additional space is used
 The space applied in the code block is basically not additional space  except for the code block, it is destroyed, such as function calls and loops
With the above foundation, we can better introduce:
Space complexity can only be represented by additional space applied
2.4.1 example drill
Example 1
void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i1] > a[i]) { Swap(&a[i1], &a[i]); exchange = 1; } } if (exchange == 0) break; } }
Circular space use
It's OK to create end only once, but have exchange and i been created repeatedly?
They are created repeatedly, but look carefully at their positions. They are all in small code blocks  they are destroyed when the curly braces come out, create destroy  create destroy... They have been reusing the same space
 end, exchange, i: constant variables
 So the spatial complexity is O(1)
Summary: the space in the cycle is constantly refreshed and reused
Example 2
long long Fib(size_t n) { if (n < 3) return 1; return Fib(n  1) + Fib(n  2); }
Space usage of function:
The stack frames of recursive functions do not run at the same time. They are opened up from left to right. Only after the left is completed and destroyed, can space be opened up for the right to run
In this way, when the red stack frame is finished, it is purple's turn; At this time, the red stack frame has been destroyed, and purple will open the stack frame in the memory space of the original red stack frame; Similarly, after purple is destroyed, green opens stack frames in the original memory space of red and purple successively. Call back and forth in the red space (the same space)

The red function call on the left, from Fib(n) to Fib(1), has been called a total of n1 times, and the subsequent calls are in the reuse space

Then the space complexity of the recursive version of Fib is O(n)
Summary: function stack frames are destroyed when they are used up, and the same space is often reused to create function stack frames
That's all for sharing in this issue. Please correct the deficiencies
Bacon's blog, make progress with you!