This is the 30th day of my participation in the Wenwen Challenge

preface

For the solution of a certain kind of problem, we may need to use algorithms to achieve, the means of implementation may also be various. Although the problem was finally solved, each solution method, that is, the algorithm still has advantages and disadvantages.

Since there is a comparison, there must be a standard to refer to, so what is the standard we refer to when evaluating the merits of an algorithm?

Algorithms are evaluated in terms of the “time” and “space” they take up during execution, which are often referred to as “time complexity” and “space complexity”.

  • Time complexity: The amount of computation required to perform an algorithm, which gives an estimate of how much the program uses the processor.
  • Space complexity: The amount of memory required to perform the current algorithm, which gives an estimate of how much the program uses the processor.

Time complexity

When it comes to time complexity, the first reaction of many of us is to run the algorithm once and print out that the execution time is the time it takes. Actually, this is not feasible because:

  • There may be many kinds of algorithms to solve a problem, one by one the workload is undoubtedly huge, outweighs the loss;
  • The software and hardware environments of different computers are different. Even if the same computer is used, the system environment is different in different time periods. The running time of the program is likely to be affected, or even lead to misjudgment in serious cases.

In the real world, we prefer to use an estimate to represent the running time of the program. The so-called valuation is the estimated, inaccurate value. Note that while an estimate can’t accurately represent the running time of an algorithm, it’s not a guesswork. It requires careful calculation.

How much time an algorithm’s program runs is not an exact (and in fact impossible) value, but an estimate based on a reasonable method.

We usually use “big O notation” to express time complexity: T(n) = O(f(n))

  • N is the factor that affects the change in complexity
  • F (n) is a complexity specific algorithm
  • O stands for direct proportion

The full name of this formula is: asymptotic time complexity of algorithms.

The big O notation is not intended to represent the actual execution time of the algorithm, but rather to represent the trend of increasing code execution time.

Let’s look at a common example:

for(let index = 0; index < n; index++){
	console.log(index);
}
Copy the code

As you can see, there are only two lines of code in this program, where:

  • The for loop executes n+1 times from index 0 to n (note that the index value is n when the loop exits);
  • There is only one statement inside the loop, and the statement is executed every time the value of index increases by 1, until the value of index is n-1, so the print statement is executed n times.

Therefore, all statements in the whole code are executed (n+1)+n times, which is 2n+1 times. The number of times each statement is executed in a data structure, also known as the frequency of the statement. The total number of times the whole code is executed, i.e. the frequency of the whole code.

A common order of time complexity

  • Constant order O (1)
  • The logarithmic order O (logN)
  • Linear order O (n)
  • Square order O (n ^ 2)
  • Cubic order O (n ^ 3)
  • Order N to the K.
  • The index order (2 ^ n)

Here only the worst-case frequency is introduced as the time complexity, but in some practical scenarios, the average value of the best-case frequency and worst-case frequency can be used as the time complexity of the algorithm.

Spatial complexity

Similar to the time complexity, the spatial complexity of an algorithm is often expressed by big O notation. Space complexity is commonly used as follows:

  • O(1)
  • O(n)
  • O (n squared)

It is important to know that each program written by the algorithm needs to occupy different sizes of storage space in the process of running, for example:

  • The storage space occupied by the program code itself;

  • If the program needs input and output data, it will also occupy a certain amount of storage space;

  • While the program is running, you may need to temporarily request more storage space.

First of all, the storage space occupied by the program itself depends on the amount of code it contains. If we want to reduce this part of the storage space, we need to implement the function while writing as short as possible.

The data input and output during the running of a program often depends on the problem to be solved, and the storage space occupied by the input and output of the program is similar even if the algorithms used are different.

In fact, the biggest influence on the spatial complexity of the algorithm is often the temporary storage space applied for during the running of the program. Programs written by different algorithms usually require very different amounts of temporary storage at runtime.

If the storage space occupied by the program is independent of the input value, the space complexity of the program is O(1). On the contrary, if they are relevant, the relationship between them needs to be further judged:

  • If the temporary space applied by the program increases linearly with the increase of input value n, the space complexity of the program is expressed by O(n).
  • If the temporary space applied by the program increases in n2 relation with the increase of input value n, the space complexity of the program is denoted by O(n2).
  • If, with the increase of input value n, the temporary space applied by the program increases in n3 relation, the space complexity of the program is expressed by O(n3).

Such as:

let m = 0;
for(let index = 0; index < 9999; index++){
	m++;
}
Copy the code

Although the value of m keeps changing with the increase of index, no new variable is generated, that is, the space occupied by the program does not change, so its space complexity is O(1).

conclusion

  1. Both time complexity and spatial complexity are estimates based on rigorous calculations and do not represent the actual situation.

  2. Time complexity and space complexity represent a trend.

  3. What we generally call time complexity and space complexity are worst-case execution trends that may be better than expected.

  4. In most business scenarios, a good algorithm pays more attention to the comparison of time complexity, while the spatial complexity can be as long as it is within a reasonable range.

~

Thanks for reading!

~

Learn interesting knowledge, meet interesting friends, shape interesting soul!

Hello everyone, I am the author of “programming Samadhi”, I am king Yi, my public account is “programming Samadhi”, welcome to pay attention, I hope you can give me more advice!

You come, with expectations, I have ink to welcome! You return, no matter gain or loss, only to yu Yun give each other!

Knowledge and skills should be paid equal attention to, internal force and external power should be repaired simultaneously, theory and practice should grasp both hands, both hands should be hard!