Writing in the front
Originally super detailed department sorted out a little bit of the release, the results found that did not send out, back to the draft box only this semi-finished product, wrote a whole day mentality breakdown. I don’t have the heart to start over, so that’s it, you always save TT
I just began to prepare for the autumn brush, and I spent a day simply understanding the sorting part of the data structure. Now I will simply sort out what I have learned. The code L in this paper comes from the part of the network, and a link will be attached at the end.
Recommend a learning data structure intuitive website: visualgo.net/zh zero basis can first look at this own understanding and then look at the article.
The evaluation index
The evaluation indexes of the sorting algorithm are mainly two:
(1) Time complexity.
O (f(n)) focuses on the growth relationship between algorithm execution time and data size, indicating that the change trend of algorithm execution time is positively correlated with F (n). As far as we know, it focuses on the loops in the algorithm, the parts where the unknown parameter n exists. So when you look at the time complexity of your code, focus first on the parts of your code that have the most loops. Common examples of time complexity are:
1) O(1) and O(n) and O(m+n)
int HelloWorld(int n) {
int i = 0; Run time 1
for(; i<n; i++) { Run time n
printf("Hello, World!"); Run time n}}Copy the codeThe execution time of the above code is (2n+2). O() is concerned with the trend of change, so the time complexity of the above code is O(n) by taking the coefficient and constant term. So you can simply look at the loop, because the top loop loops n times so the time is O(n), if there are no three quarters of lines there is no loop, in which case the execution time is constant no matter how many lines of code there are, then the time is O(1).
int HelloWorld(int n,int m) {
int i = 0; Run time 1
for (; i<n; i++) { Run time n
printf("Hello, World!"); Run time n
}
for(int j=0; j<m; j++){printf("hey!"); }}Copy the codeLet’s focus on the loop. For the two loops above, the time complexity is O(n+m) because the magnitude of m and n cannot be determined.
2) O(n ^ 2) and O(m*n)
int HelloWorld(int n) {
int i = 0; Run time 1
for(; i<n; i++) { Run time n
for(int j = 0; j<n; J++) {Run time n
printf("Hello, World!"); }}Copy the codeSo if you have a nested loop like this and you use multiplication, and you focus on the loop, the time is O(n ^ 2), and if you have j
3) O (logn) and O (nlogn)
int HelloWorld(int n) {
int i = 1;
while( i<n) { i=i*2; }}Copy the codeIf you look at the loop, you might think, shouldn’t this be order (n), but if you look at the n, don’t forget to look at the other parameter I of the loop, the cut-off condition is I
int HelloWorld(int n) {
int i = 1;
for(int j = 0; j<n; J++) {while( i<n) { i=i*2; }}}Copy the codeIf we have a loop loop like (2), that is, an n loop, the time complexity is O(nlogn).
Time complexity and best, worst, average complexity. The best-case time complexity is, in the best case, the time complexity of executing this code. The worst-case time complexity is, in the worst case, the time complexity of executing this code. The average time complexity is the average case time complexity. I didn’t go to see it specifically, and I will supplement it later when I have time.
(2) Spatial complexity
As opposed to time complexity, space complexity refers to the trend in the amount of storage temporarily occupied by code during runtime. Also expressed by O() function to represent the growth relationship between algorithm storage space and data size.
1) O(1)
int HelloWorld(int n) {
int i = 1;
while( i<n) { i=i*2; }}Copy the codeLike the code above, although it has a loop, the amount of temporary space it needs is not proportional to n, so it is a constant. That’s O (1).
2) O(n)
int HelloWorld(int n) {
int [] list = new int[n];
int i = 1;
while( i<n) { i=i*2; }}Copy the codeIn the last code, we allocated an array space of length N, so it was order n.