Time complexity and space complexity

1、 Preface

Algorithm (Algorithm） It is used to operate data 、 A set of solutions to procedural problems . For the same question , Using different algorithms , Maybe the end result is the same , But the resources and time consumed in the process will be very different .

So how should we measure the advantages and disadvantages of different algorithms ？

Mainly from the occupied by the algorithm 「 Time 」 and 「 Space 」 Two dimensions to consider .

• Time dimension ： The time spent executing the current algorithm , We usually use [ Time complexity ] To describe .
• Spatial dimension ： It refers to the memory space required to execute the current algorithm , We usually use [ Spatial complexity ] To describe .

therefore , The efficiency of an algorithm mainly depends on its time complexity and space complexity . However , Sometimes time and space are 「 Fish and bear paw 」, Not both , Then we need to strike a balance .

Let me introduce them separately 「 Time complexity 」 and 「 Spatial complexity 」 Calculation method of .

Two 、 Time complexity

We want to know the of an algorithm 「 Time complexity 」, The first way many people think of is to run the algorithm program again , Then the time it takes will naturally know .

Is this way OK ？ Certainly. , But it also has many disadvantages .
This approach is very vulnerable to the operating environment , The results of running on high-performance machines will be very different from those on low-performance machines . And it also has a great relationship with the size of the data used in the test . also , And when we write algorithms , There is no way to run it completely .

therefore , Another more general method came out ：「 Big O Symbolic representation 」, namely T(n) = O(f(n))

Let's start with an example ：

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

adopt 「 Big O Symbolic representation 」, The time complexity of this code is ：O(n) , Why? ?
At large O In symbolic representation , The formula of time complexity is ：T(n) = O( f(n) ), among f(n) Represents the sum of execution times per line of code , and O Represents a positive proportional relationship , The full name of this formula is ： Progressive time complexity of the algorithm .

Let's continue with the example above , Suppose that the execution time of each line of code is the same , We use it 1 Particle size is expressed by time , So the first line of this example takes 1 Particle time , The execution time of the third line is n Particle time , The execution time of the fourth line is also n Particle time （ The second and fifth lines are symbols , Temporary neglect ）, So the total time is 1 Particle time + n Particle time + n Particle time , namely （1+2n） Particle time , namely ：T(n) = (1+2n)* Particle time , From this result, we can see that , This algorithm takes time n Change by change , therefore , We can simply express the time complexity of this algorithm as ：T(n) = O(n)