The ultimate purpose of studying algorithms is how to spend less time and occupy less memory to complete the same requirements. Cases also demonstrate the differences in time and space consumption between different algorithms, but we can't use time and space. Therefore, Next, we will learn about the description and analysis of algorithm time consumption and algorithm space consumption. The time consumption analysis of the algorithm is called the time complexity analysis of the algorithm, and the space consumption analysis of the algorithm is called the space complexity analysis of the algorithm.
1. Time complexity
1. Large scale notation
When analyzing the algorithm, the total execution times T(n) of the statement is a function of the problem scale n, and then analyze the change of T(n) with N and determine the magnitude of T(n). The time complexity of the algorithm is the time measurement of the algorithm, which is recorded as: T(n)=O(f(n)). It means that with the increase of the problem scale n, the growth rate of the algorithm execution time is the same as that of f(n), which is called the asymptotic time complexity of the algorithm, or time complexity for short, where f(n) is a function of the problem scale n.
Here, we need to clarify one thing: execution times = execution time
The notation of using capital O() to reflect the time complexity of the algorithm is called large o notation. Generally, with the increase of input scale n, the algorithm with the slowest growth of T(n) is the optimal algorithm.
Case 1:
public static void main(String[] args) {
int sum = 0;//Execute once
int n=100;//Execute once
sum = (n+1)*n/2;//Execute once
System.out.println("sum="+sum);
}
Case 2:
public static void main(String[] args) {
int sum = 0;//Execute once
int n=100;//Execute once
for (int i = 1; i <= n; i++) {
sum += i;//Executed n times
}
System.out.println("sum=" + sum);
}
Case 3:
public static void main(String[] args) {
int sum=0;//Execute once
int n=100;//Execute once
for (int i = 1; i <=n ; i++) {
for (int j = 1; j <=n ; j++) {
sum+=i;//Execute n^2 times
}
}
System.out.println("sum="+sum);
}
If the execution times of judgment conditions and output statements are ignored, when the input scale is n, the execution times of the above algorithms are respectively:
Case 1: 3 times
Case 2: n+3 times
Case 3: n^2+2 times
Based on our analysis of the asymptotic growth of the function, the following rules can be used to derive the representation of large order O:
- Replace all addition constants in the running time with constant 1;
- In the modified run times, only high-order items are retained;
- If the highest order term exists and the constant factor is not 1, remove the constant multiplied by this term;
Therefore, the corresponding three cases above are:
Case 1: O(1)
Case 1: O(n)
Case 1: O(n^2)
2. Common large order O
1. Linear order
Generally, non nested loops involve linear order, which means that the number of corresponding calculations increases linearly with the expansion of input scale
public static void main(String[] args) {
int sum = 0;
int n=100;
for (int i = 1; i <= n; i++) {
sum += i;
}
System.out.println("sum=" + sum);
}
In the above code, the time complexity of the loop is O(n), because the code in the loop body needs to be executed n times
2. Square order
Generally, nested loops belong to this time complexity
public static void main(String[] args) {
int sum=0,n=100;
for (int i = 1; i <=n ; i++) {
for (int j = 1; j <=n ; j++) {
sum+=i;
}
}
System.out.println(sum);
}
In the above code, n=100, that is, every time the outer loop is executed, the inner loop is executed 100 times. In total, if the program wants to get out of these two loops, it needs to be executed 100 times, that is, the square of N, so the time complexity of this code is O(n^2)*
3. Cubic order
Generally, three-level nested loops belong to this time complexity
public static void main(String[] args) {
int x=0,n=100;
for (int i = 1; i <=n ; i++) {
for (int j = i; j <=n ; j++) {
for (int j = i; j <=n ; j++) {
x++;
}
}
}
System.out.println(x);
}
In the above code, n=100, that is, every time the outer loop is executed, the intermediate loop is executed 100 times, and every time the intermediate loop is executed, the innermost loop needs to be executed 100 times. In total, if the program wants to get out of these three loops, it needs to be executed 100 times, that is, the cube of N, so the time complexity of this code is O(n^3)
4. Logarithmic order
Logarithm is the content of high school mathematics. Our analysis program is mainly program, supplemented by mathematics
int i=1,n=100;
while(i<n){
i = i*2;
}
Since it is one step closer to n after each i2, if there are x 2 times greater than N, it will exit the loop. Since it is 2^x=n, x=log(2)n is obtained, so the time complexity of this cycle is O(logn)*
5. Constant order
Generally, the constant order does not involve cyclic operation, because it will not increase the number of operations with the increase of n.
public static void main(String[] args) {
int n=100;
int i=n+2;
System.out.println(i);
}
The above code is executed twice regardless of the input scale n. according to the large o derivation rule, the constant is replaced with 1, so the time complexity of the above code is O(1)
The order of complexity from low to high is O (1) < o (logn) < o (n) < o (nlogn) < o (N2) < o (N3)
3. Time complexity analysis of function call
Case 1:
public static void main(String[] args) {
int n=100;
for (int i = 0; i < n; i++) {
show(i);
}
}
private static void show(int i) {
System.out.println(i);
}
In the main method, there is a for loop. The loop body calls the show method. Because only one line of code is executed inside the show method, the time complexity of the show method is O(1), and the time complexity of the main method is O(n)
Case 2:
public static void main(String[] args) {
int n=100;
for (int i = 0; i < n; i++) {
show(i);
}
}
private static void show(int i) {
for (int j = 0; j < i; i++) {
System.out.println(i);
}
}
In the main method, there is a for loop. The loop body calls the show method. Because there is also a for loop inside the show method, the time complexity of the show method is O(n), and the time complexity of the main method is O(n^2)
Case 3:
public static void main(String[] args) {
int n=100;
show(n);
for (int i = 0; i < n; i++) {
show(i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println(j);
}
}
}
private static void show(int i) {
for (int j = 0; j < i; i++) {
System.out.println(i);
}
}
In the show method, there is a for loop, so the time complexity of the show method is O(n). In the main method, the internal execution times of the show(n) line of code are n. The first for loop calls the show method, so its execution times are NN. In the second nested for loop, only one line of code is executed, so its execution times are NN. Then the total execution times of the main method is n+n2+n2=2nn+n. According to the large o derivation rule, remove n, retain the highest order term, and remove the constant factor 2 of the highest order term, so the time complexity of the final main method is O(n^2)*
4. Worst case scenario
There is an array that stores n random numbers. Please find the specified number from it.
public int search(int num){
int[] arr={11,10,8,9,7,22,23,0};
for (int i = 0; i < arr.length; i++) {
if (num==arr[i]){
return i;
}
}
return -1;
}
The best case: if the first number found is the expected number, the time complexity of the algorithm is O(1)
Worst case: if the last number found is the expected number, the time complexity of the algorithm is O(n)
Average case: the average cost of any number lookup is O(n/2)
2. Spatial complexity
1. Common memory occupation in Java
| data type | Occupied bytes |
|---|---|
| byte | 1 |
| short | 2 |
| int | 4 |
| long | 8 |
| float | 4 |
| double | 8 |
| boolean | 1 |
| char | 2 |
A reference (machine address) needs 8 bytes to represent:
For example: date = new date(), the date variable needs to take 8 bytes to represent
- Create an object, such as new Date(). In addition to the memory occupied by the data stored inside the Date object (such as year, month, day and other information), the object itself also has memory overhead. The overhead of each object is 16 bytes, which is used to save the header information of the object.
- General memory usage, if less than 8 bytes, will be automatically filled into 8 bytes
- In java, arrays are limited to objects. They generally need additional memory because of the record length. An array of original data types generally needs 24 bytes of header information (16 own object overhead, 4 bytes for saving length and 4 padding bytes) plus the memory required to save values.
2. Spatial complexity
The calculation formula of the spatial complexity of the algorithm is recorded as: S(n)=O(f(n)), where n is the input scale and f(n) is the function of the storage space occupied by the statement with respect to n.
Case: invert the specified array element and return the inverted content.
Solution 1:
public static int[] reverse2(int[] nums){
int n = nums.length;//Request 4 bytes
int temp;//Request 4 bytes
for (int start = 0,end = n-1; start < end; start++,end--) {
temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
}
return nums;
}
Solution 2:
/**
* Array inversion
* @param nums
* @return
*/
public static int[] reverse(int[] nums){
int n = nums.length;//Request 4 bytes
int[] resultArr = new int[n];//Apply for n*4 bytes + 24 bytes of header information overhead of the array itself
for (int i = n - 1; i >= 0; i--) {
resultArr[n - 1 - i] = nums[i];
}
return resultArr;
}
Solution 1: regardless of the size of the incoming array, always apply for 4 + 4 = 8 bytes; Space complexity is O(1)
Solution 2: 4+4n+24=4n+28; The space complexity is O(n)
From the perspective of space occupation, solution one is better than solution two