What is the complexity often said during the interview?

When we were interviewing , There are always interviewers who like to ask , Time complexity , Spatial complexity , Like O(n²) such , So how is this time complexity defined , Why use this definition , Finally, what does time complexity mean about your program ？ Today, let's talk about our own views on complexity .

Algorithm

Speaking of complexity , Then it must have something to do with your own algorithm , Then someone will always say , I don't know what the algorithm is , But it doesn't delay me to be a developer . That's what they say , But you have to think about , If you are interviewing a big factory , The interviewer asked him , Then you can say , Although I'm not very good at , But I can work , I guess the interviewer may not believe you either . At work , Just ask the program to run , Not too concerned about performance , So try to avoid the pit （ArrayList Or LinkedList）, Which is easy to use which , But as long as the interview to the data structure and Algorithm , There is no doubt about kneeling .

From a professional background , There must be some concepts about Algorithm , Because the university may learn data structures and algorithms , But if you just want to pass the exam , I didn't say .

So what is the algorithm ？

Algorithm （Algorithm） It refers to the accurate and complete description of the solution , It's a series of clear instructions to solve problems , Algorithms represent a systematic approach to describe the policy mechanisms for solving problems .

The algorithm is actually spoken in popular language , That's a way of thinking to end the problem , Algorithm , There is no right or wrong. , But there is a difference between good and bad .

For example, the most common algorithm in our daily life, such as the algorithm in sorting

• Bubble sort
• Quick sort
• Insertion sort
• Merge sort
• Count sorting

There are other algorithms ,LRU Algorithm ,LFU Algorithm ,Hash Algorithm these , All of them can achieve the same function , however , No mistake , It's about efficiency , There is also the problem of time complexity .
What is the time complexity ？

Time complexity

Big O Complexity representation

actually , Speak straight and white , It's the algorithm you wrote , Running time , And this time is at the design level , It can be called time complexity .

We assume that the time to execute a line of code is t, By estimating , Code execution time T(n) It is proportional to the number of executions , Remember to do :

T(n)=O(f(n))

• T(n)： Code execution time
• n： Data scale
• f(n)： The sum of the execution times of each line of code
• O： The execution time of the code is the same as f(n) The expression is proportional to

Let's look at a simple case

int sum(int n)
{ 
  int s=0; //t 
  int i=1; //t 
  for(;i<=n;i++){ //t*n 
  s=s+i; //t*n 
}
return s; //t } 

n=100 
1+1+100n+100n+1=200n+2

It looks like this , We can see the time complexity according to this formula ,

T(n)=O(2n+2)

But we tested it from an infinite angle , When n In infinity , The low order 、 Constant 、 The system can ignore , This is equivalent to ：

T(n)=O(n)

This complexity belongs to , Is that the code execution time increases with the increase of data size , That is, the larger the data scale , The longer the code execution time is required , This is one of the algorithms .

Several common time complexity .

• O(1) Constant order

This expression means , Constant level time complexity , That is, it will not grow with the growth of data , But a constant value to calculate , This kind of time complexity does not exist , But relatively few .

• O(logn)、O(nlogn) Logarithmic order ( linear )

A simple example is as follows ：

i = 1; 
while(i <= n)
{ 
	i = i * 2;//  Execution is the most  
}

And this time x=log₂ n

The neglect factor is logn

T(n)=O(logn）

If you execute this code n All over , Then the time complexity is recorded as :

T(n)=O(n*logn）, namely O(nlogn)

In fact, there are many , Like

• O(nⁿ) n Square steps

In fact, this belongs to the best understood , For example, we write nested for loop , It belongs to n Square steps , How many cycles do you have , That's how many steps

Sample code ：

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

• O(2ⁿ) Exponential order
• O(n!) Factorial stage

Actually, I see this , Everyone must also feel it , It has a lot to do with Mathematics , This is also the reason why some companies require you to be good at Advanced Mathematics .

best 、 The worst 、 Average 、 Average time complexity

In fact, this is the most difficult one , Because a lot of times , To understand this, we need to understand it from the code level , The worst , Average , The average time complexity .

For example, the following code ：

    /**
     *  Find the position of a given element in a given array , If we can't find a way back -1
     * @param arr  Given array 
     * @param target  Given element 
     * @return
     */
    public int find(int[] arr, int target) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            //  Traverse the array in turn , If you find the same value as the target element , The subscript where the value is returned 
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

1. Best case time complexity ： The target element is just in the first position of the array , Then it only takes one time to find , The time complexity is obviously constant O(1).

2. Worst case time complexity ： The target element is at the last position of the array or not in the array , Then you need to traverse the entire array to get the result , The time complexity is O(n).

Because the location of the target element is different , This leads to an order of magnitude difference in time complexity . In this case, we need to consider the average time complexity , Here is a brief analysis of ： If the target element is in the array , There are n In this case , Add the case that it is not in the array , in total n+1 In this case . The number of iterations in each case is shown in the following table ：

The relationship between the location of the target element and the number of iterations

The first 1 A place	Traverse 1 Time
The first 2 A place	Traverse 2 Time
The first 3 A place	Traverse 3 Time
The first n A place	Traverse n Time
Not in array	Traverse n Time

Average number of iterations = The number of iterations in each case is added ÷ The total number of cases .

If we ignore the coefficients and lower order terms , Then the calculation formula becomes

Before ignoring

（1+2+3+…+n+n）/（n+1） = n(n+3) /2(n+1)

After ignoring , Calculation becomes n

In other words, his average time complexity becomes T(n) = O(f(n)) = O(n).

In fact, many people say , Calculating this average time complexity makes no sense , It's not , It is actually a standard to measure the running time of programs , That's the only way , We can see the good of this algorithm , Or bad? , Do you think that's right ？

After we finish this time complexity , We need to start to care about the complexity of this space , So what is spatial complexity ？

Spatial complexity

All our time complexity , It refers to the running time of the program , Then the space complexity is the same , Refers to the time when the program is running , The space needed , Remember to do S(n)=O(f(n)).

In fact, space complexity and time complexity are quite interesting things , For an algorithm , His time complexity and space complexity often interact .

When pursuing a better time complexity , It may make the performance of space complexity worse , Can lead to more storage space ;

conversely , When pursuing a better spatial complexity , It may make the performance of time complexity worse , Can lead to a longer running time .

And this time complexity and space complexity are combined , It can be called complexity .

Do you understand ？