catalogue
Time complexity and space complexity
2.1 concept of time complexity
2.2 progressive representation of large O
2.3 common time complexity calculation examples
Time complexity and space complexity
1. Algorithm 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 stage of computer development, the storage capacity of the computer is very small. So I care about the complexity of space. However, with the rapid development of computer industry, the storage capacity of computer has reached a high level. Therefore, we no longer need to pay special attention to the spatial complexity of an algorithm.
2. Time complexity
2.1 concept of time complexity
Definition of time complexity: in computer science, the time complexity of an algorithm is a function that quantitatively describes the running time of the algorithm. In theory, the time spent in the execution of an algorithm cannot be calculated. You can only know when you put your program on the machine and run it. But do we need every algorithm to be tested on the computer? Yes, it can be tested on the computer, but it is very troublesome, so there is the analysis method of time complexity. The time spent by an algorithm is directly proportional to the execution times of the statements in it. The execution times of the basic operations in the algorithm is the time complexity of the algorithm.
2.2 progressive representation of large O
Big O notation: a mathematical symbol used to describe the asymptotic behavior of a function.
Derivation of large O-order method:
1. Replace all addition constants in the running time with constant 1.
2. In the modified run times function, only the highest order term is retained.
3. If the highest order term exists and is not 1, remove the constant multiplied by this item. The result is large O-order.
In addition, the time complexity of some algorithms has the best, average and worst cases:
- Worst case: maximum number of runs 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)
For example, search for a data x in an array of length N
Best case: 1 time
Worst case: found N times
Average: N/2 times
In practice, we usually focus on the worst-case operation of the algorithm, so the time complexity of searching data in the array is O(N)
2.3 common time complexity calculation examples
Example 1: time complexity of ordinary loop
// Please calculate how many times func1 basic operations have been performed?
void func1(int N){
int count = 0;
for (int i = 0; i < N ; i++) {
for (int j = 0; j < N ; j++){
count++;}
}
for (int k = 0; k < 2 * N ; k++)
{count++;}
int M = 10;
while ((M--) > 0)
{count++;}
System.out.println(count);
}
Analytical diagram:
Time complexity: O(N^2)
Example 2: time complexity of ordinary loop
// 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);
}
Analytical diagram:
Time complexity: O(N)
Example 3: time complexity of loop
// 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);
}
Analytical diagram:
Time complexity: O(M+N)
Example 4: time complexity of loop
// 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);
}
Analytical diagram:
Time complexity: O(1)
Example 5: time complexity of bubbling function
// Calculate the time 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;
}
}
}
Analytical diagram:
Time complexity: O(N^2)
Example 6: time complexity of binary search
// Calculate the time complexity of binarySearch?
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;
}
Analytical diagram:
Time complexity: O(log2N) (base 2 here)
Example 7: time complexity of factorial recursion
// The time complexity of computing factorial recursive factorial?
long factorial(int N) {
return N < 2 ? N : factorial(N-1) * N;
}
Analytical diagram:
Time complexity: O(N)
Example 8: time complexity of fiboracci sequence
// Computing the time complexity of fibonacci recursive fibonacci?
int fibonacci(int N) {
return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}
Analytical diagram:
Time complexity: O(2^n)
3. Space complexity
Space complexity is a measure of the amount of storage space temporarily occupied by an algorithm during operation.
Space complexity is not how many bytes the program occupies, because it doesn't make much sense, so space complexity is the number of variables. The calculation rules of spatial complexity are basically similar to the practical complexity, and the large O asymptotic representation is also used.
Example 1: spatial complexity of bubbling function
// 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;
}
}
}
Example 2: spatial complexity of fiboracci sequence
// How to calculate the spatial complexity 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;
}
Example 3: space complexity of factorial recursion
// The time complexity of computing Factorial recursive Factorial?
long factorial(int N) {
return N < 2 ? N : factorial(N - 1) * N;
}
1. Example 1 uses two additional spaces, so the space complexity is O(1)
2. Example 2 dynamically opens up N spaces with a space complexity of O(N)
3. Instance 3 recursively called N times, opened up N stack frames, and each stack frame used a constant space. Space complexity is O(N)