preface
This is the fifth day of my participation in Gwen Challenge
I want that Nuggets T-shirt, I love it…
algorithm
An Algorithm is a clearly specified set of simple instructions to follow to solve a problem.
The evaluation of an algorithm is mainly based on time complexity and space complexity. Time complexity is a function that qualitatively describes the running time of the algorithm, usually represented by the big O symbol.
Common time complexity is O(1),O(logn),O(n),O(n^2),O(2^n)… And so on.
Now let’s talk about how time complexity is calculated.
Time complexity
In computer science, time complexity, also known as time complexity, is a function that qualitatively describes the running time of an algorithm. This is a function that represents the length of the string input to the algorithm. The time complexity is often expressed in large O notation, excluding the lower order and leading coefficients of the function. In this way, the time complexity can be said to be asymptotic, that is, as the size of the input approaches infinity.
Time complexity calculation
We define the number of statements executed in the algorithm as statement frequency or time frequency T(n). That is, T(n) is the number of times the program is executed.
Method 1 is executed how many times:
public int method1(a){
System.out.println("hello"); // Execute once
return 0; // Execute once
}
Copy the codeYeah, it’s executed internally twice.
So let’s look at the following method 2 several times:
public int method2(int n){
for(int i = 0; i<n ; i++){
// I = 0 execute once, I
System.out.println("hello"); // Execute the output statement n times
}
return 1; //return executes once
}
Copy the codeYeah, it did 3n plus 3 times. So T(n) = 2 for method 1; For method 2, T of n is equal to 3n plus 3.
The actual code is certainly much more complex than the code in the example, and it is obviously impossible to count the number of times the code is executed, so algorithms generally use asymptotic estimates of T(n) to reflect the speed of code execution. This estimate is expressed in terms of time complexity.
Therefore, for method 1 and method 2, how to estimate the time complexity according to T(n) :
- For T(n) = 2, since T(n) is a constant, the time complexity can be directly estimated as 1. So T(n) = 2 has time complexity 1. The standard time complexity function is O(1).
- For T(n) = 3n + 3, the constant 3 is negligible with respect to 3n as the value of n increases. And the coefficient is usually estimated to be 1. It is equivalent to removing the coefficients and constants, then the time complexity is N. It’s O(n) in terms of time complexity.
- For T(n) = 3n^2 + 3n + 3. As the value of n increases, the growth of the term behind the polynomial is far less than that of n^2. The lower order term and constant term can be directly discarded, so only the term with the largest power of n can be retained, so its time complexity is O(n^3).
Summarize the above rules:
- T(n) is constant: the time complexity is O(1);
- T(n) is not constant: the time complexity is O(T(n) of the highest degree and the coefficient of the highest degree is removed).
Common time complexity
The time complexity of method 1 is O(1) :
// Time complexity is O(1)
public void m1(a){
System.out.println("A");
System.out.println("B"); . System.out.println("L");
}
Copy the codeThe time complexity of method 2 is O(n) :
// The time complexity is O(n)
public int method2(int n){
for(int i = 0; i < n ; i++){
System.out.println("a");
}
return 1;
}
Copy the codeTime complexity of method 3 is O(n^2) :
// Time complexity is O(n^2)
public void method3(int n){
for(int i = 0; i < n ; i++){
for(int j = 0 ; j < i ; j ++){
System.out.println("a"); }}}Copy the codeThe time complexity of method 4 is O(logn) :
public void method4(int n){
int i = 1;
while(i<n)
{
i = i * 2; }}Copy the codeAs you can see from the code above, in the while loop, every time I is multiplied by 2, I gets closer and closer to n. So let’s try to solve for it, assuming that after x times, I is greater than 2, and then the loop ends, which means that 2 to the x is equal to n, so x is equal to log2 to the n which means that after x to the log2 to the n, this code ends. So the time complexity of this code is O(logn).
The time complexity of method 5 is O(nlogN) :
public void method5(int n) {
for (int m = 1; m < n; m++) {
int i = 1;
while (i < n) {
i = i * 2; }}}Copy the codeLinear log order O(N logn) is actually very easy to understand, so if I loop O(logn) code N times, it’s N times O(logn), which is order N (logn).
Generally, the common time complexity is sorted as follows (from fast to slow).
Let’s graph the time complexity.
It can also be seen from the figure that the exponential and factorial levels grow fastest as the number of elements increases. It’s obviously the least efficient.
Differences in time complexity
Let’s take an example:
The relative time scale of algorithm A is T (n) = 100N and the time complexity is O(n).
The relative time scale of algorithm B is T (n) = 5n^2 and the time complexity is O(n^2).
Algorithm A runs on an old computer, and algorithm B runs on A supercomputer that’s 100 times faster.
So, as the input size n increases, which of the two algorithms will run faster?
As can be seen from the table, when the value of n is very small, the running time of algorithm A is much larger than that of algorithm B. When the value of n reaches about 1000, the running time of algorithm A and algorithm B is close. When the value of N becomes larger and larger, reaching one hundred thousand or one million, the advantage of algorithm A begins to appear, while algorithm B becomes slower and slower, and the gap becomes more and more obvious.
This is the difference in time complexity.
conclusion
To learn algorithms well, one must understand time complexity as an important cornerstone. Through the above analysis, I believe we have a certain understanding of time complexity, we make progress together, come on.