Time complexity and space complexity
Algorithmic efficiency
There are two kinds of algorithm efficiency analysis: * * the first is time efficiency and the second is space efficiency** Time efficiency is called time complexity, and space efficiency is called space complexity. Time complexity mainly measures the running speed of an algorithm, while space complexity mainly measures the additional space required by an algorithm,
In the early days of computer development, the storage capacity of computer was very small. So I care about the complexity of space. However, with the rapid development of the computer industry, the storage capacity of the computer has reached a very high level. Therefore, we no longer need to pay special attention to the spatial complexity of an algorithm.
Asymptotic representation of large O
In fact, when we calculate the time complexity, we do not have to calculate the exact execution times, but only the approximate execution times. Here, we use the asymptotic representation of big O.
Big O notation: a mathematical symbol used to describe the asymptotic behavior of a function. How to deduce here can be seen by Baidu (as a weak mathematical chicken, I feel dizzy...) we only need to remember its three conclusions:
1. Replace all addition constants in the run time with constant 1.
2. In the modified run times function, only the highest order term is reserved.
3. If the highest order term exists and is not 1, the constant multiplied by this item is removed. The result is large order O.
In addition, the time complexity of some algorithms has the best, average and worst cases:
Worst case: maximum operation times of any input scale (upper bound)
Average case: expected number of runs of any input scale
Best case: minimum number of runs of any input scale (lower bound)
In the actual development, we usually focus on the maximum running times of the algorithm in the worst case, which is used to express the time complexity of the algorithm
Time complexity
concept
Definition of time complexity: in computer science, the time complexity of an algorithm is a mathematical function that quantitatively describes the running time of the algorithm** Theoretically speaking, the time spent in the execution of an algorithm cannot be calculated. Only when you put your program on the machine and run it, can you know. But do we need to test every algorithm on the computer? Yes, it can be tested on the computer, but it is very troublesome, so the time complexity analysis method is available. The time spent by an algorithm is in direct proportion to the number of statements executed. The number of basic operations executed in the algorithm is the time complexity of the algorithm. Time complexity must be calculated in combination with the idea of code, not just by code.
Example 1
// Calculate the time complexity of func2?
void func2(int N) {
int count = 0;
for (int k = 0; k < 2 * N ; k++) {
count++;
}
int M = 10;
while ((M--) > 0) {
count++;
}
System.out.println(count);
}
Answer and analysis: in the above code, K executes 2 * N times and M executes 10 times A total of 2*N+10 times were performed. We know that the time complexity is O(N) through the large O-order method (the addition constant is taken as 1, the constant multiplied by the highest order is set as 1, and finally only the highest order items are retained and the rest are removed)
Example 2
// Calculate the time complexity of func3?
void func3(int N, int M) {
int count = 0;
for (int k = 0; k < M; k++) {
count++;
}
for (int k = 0; k < N ; k++) {
count++;
}
System.out.println(count);
}
Answer and analysis: the code has been executed M+N times, and there are two unknowns M and N. note that this is an unknown number, which may be an exponent or a constant. Therefore, it cannot be taken as a constant to take O(1) So the time complexity is O(N+M)
Example 3
// Calculate the time complexity of func4?
void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
count++;
}
System.out.println(count);
}
Answer and analysis: the code has been executed for 100 times. By deriving the large order o method, the time complexity is O(1)
Example 4
// Calculate the time complexity of bubbleSort? (bubble sort)
void bubbleSort(int[] array) {
for (int end = array.length; end > 0; end--) {
boolean sorted = true;
for (int i = 1; i < end; i++) {
if (array[i - 1] > array[i]) {
Swap(array, i - 1, i);
sorted = false;
}
}
if (sorted == true) {
break;
}
}
}
Answer and analysis: in the above code, the outer loop for is executed N-1 times, and the inner loop is an arithmetic sequence. The number of comparisons decreases once each time The formula is (N-1)*(1+N-1)/2 After finishing (N^2 - N)/2 The best code execution is N times, and the worst is (N*(N-1))/2 times. Generally, the worst case is considered by deriving the large O-order method + time complexity, and the time complexity is O(N^2)
Example 5
// Calculate the time complexity of binarySearch? (binary search)
int binarySearch(int[] array, int value) {
int begin = 0;
int end = array.length - 1;
while (begin <= end) {
int mid = begin + ((end-begin) / 2);
if (array[mid] < value)
begin = mid + 1;
else if (array[mid] > value)
end = mid - 1;
else
return mid;
}
return -1;
}
Answer and analysis: the code operation is executed once at best, and the worst time complexity is O(log2N). In the algorithm analysis, log2 N means that the base number is 2 and the logarithm is N. in some places, it will be written as lgN. (calculate the logN through origami search) (because half of the unsuitable values are excluded each time for binary search, one binary is left: n/2, two binary is left: n/2 = N/4)
Example 6
// Time complexity of computing factorial recursive factorial?
long factorial(int N) {
return N < 2 ? N : factorial(N-1) * N;
}
Answer and analysis: the time complexity of recursion = the number of recursions * the number of recursion executions. The code above finds that the number of basic recursions is N-1, and the number of recursion executions is 1 The time complexity is O(N).
Example 7
// Calculate the time complexity of fibonacci recursive fibonacci?
int fibonacci(int N) {
return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}
Answer and analysis: the code recurses 2^N times, and the time complexity is 0(2^N).
Spatial complexity
Space complexity is a measure of the amount of storage space temporarily occupied by an algorithm during operation. The space complexity is not how many bytes the program occupies, because it doesn't make much sense, so the space complexity is the number of variables. The space complexity calculation rules are basically similar to the time complexity, and the large O asymptotic representation is also used.
Example 1
// Calculate the spatial complexity of bubbleSort?
void bubbleSort(int[] array) {
for (int end = array.length; end > 0; end--) {
boolean sorted = true;
for (int i = 1; i < end; i++) {
if (array[i - 1] > array[i]) {
Swap(array, i - 1, i);
sorted = false;
}
}
if (sorted == true) {
break;
}
}
}
Answer and analysis: the code uses constant extra space, because only three additional variables end, sorted, and I are created in the code. Each loop is reused So the space complexity is O(1)
Example 2
// Calculate the spatial complexity of the nth term of fibonacci?
int[] fibonacci(int n) {
long[] fibArray = new long[n + 1];
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n ; i++) {
fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
}
return fibArray;
}
Answer and analysis: the code is new long[n + 1]. Item n opens up n+1 spaces, and the space complexity is O(N)
Example 3
// Calculate the space complexity of Factorial recursive Factorial?
long factorial(int N) {
return N < 2 ? N : factorial(N-1)*N;
}
Answer and analysis: the code recursively calls N times and opens up N stack frames. Each stack frame uses a constant space. Space complexity is O(N)
Sort by size: O (1) < o (logn) < o (n) < o (n*logn) < o (n^2) < o (2^n)
Exercise 1
class Solution {
public int firstUniqChar(String s) {
int[] count = new int[256];
// Count the number of occurrences of each character
for(int i = 0; i < s.length(); ++i){
count[s.charAt(i)]++;
}
// Find the first character that appears only once
for(int i = 0; i < s.length(); ++i){
if(1 == count[s.charAt(i)]){
return i;
}
}
return -1;
}
}
Answer: time complexity O(N), space complexity O(1)
Exercise 2
public boolean isPalindrome(String s) {
// Unify case
s = s.toLowerCase();
int left = 0, right = s.length()-1;
while(left < right){
// 1. find a valid character from the left
while(left < right && !isValidChar(s.charAt(left))){
left++;
}
// 2. find a valid character from the right
while(left < right && !isValidChar(s.charAt(right))){
right--;
}
if(s.charAt(left) != s.charAt(right)){
return false;
}else{
left++;
right--;
}
}
return true;
}
Answer: time complexity O(N), space complexity O(1)
Note: the time complexity mentioned at the beginning must be calculated in combination with the idea of the code, not just by the code So don't be confused by the nesting of loops in the code. In essence, there are still while (left < right) O (n) outer loops, and the inner loop is just the constant comparison judgment of O(1)
All right, guys, this chapter is over Please click three times to make progress together!