Big O notation interpretation

When comparing the performance of the algorithm , It is not only related to the speed and space of the same data item , What is more important is the degree of change with the data items when the data volume changes , Big O Recording and sending is the curve of the time complexity and space complexity of the algorithm changing with the data item , Because the shape of a polynomial curve is usually determined by the highest order term , When the amount of data is relatively high, the influence of the lower order term is very small relative to the highest order term, which can be ignored for convenience .

• Time complexity ：

Simply put, the time complexity increases with N An increase in , The number of times the program needs to run varies with N The curve of change . A function in the algorithm has n Repeat the basic operation for times , use T(n) Express , Now there is some auxiliary function f(n), Properly n Approaching infinity ,T（n)/f(n) The limit value of is a constant not equal to zero , said f(n) yes T(n) Functions of the same order of magnitude of . Write it down as T(n)=O(f(n)), call O(f(n)) Is the incremental time complexity of the algorithm , Time complexity
Take a simple chestnut ：

   sum=0;                
   for(i=0;i<n;i++)  
   		for(j=0;j<n;j++) 
       		sum++;

First line frequency 1, The second line n, The third line n², In the fourth row n²,T(n)=2n²+n+1 =O(n²) The time complexity is
O（n²）

• Spatial complexity ：

The space complexity of an algorithm is defined as the storage space consumed by the algorithm , The consumption of storage space is determined by the number of objects created in the function , That is, the spatial complexity depends on the number of objects created in the function, and the calculation method of time complexity is similar . In recursion, each recursion always uses space and N Approximate curvilinear relationship of .
for example ：

  int fun(int n)
    {
     
        int num = 1;
        if(n <= num )
           return 1;
        else
          return n*fun(n-1);
    }

Recursive space complexity ：
O(n)=n*1=n;
The number of recursions is n Time , Every time you enter create 1 Objects

summary , Big O The advantage of memorization is simplicity , Understandability , But the disadvantage is that it is too simple , such as O(n) and O(5n) It is the same. It is also recorded as O(n), So when the amount of data is the same, obviously O(n) Faster , Recognizing this is more accurate in algorithm analysis .