1. What are time complexity and space complexity?
1.1 Algorithm efficiency
Algorithm efficiency analysis is divided into two types: the first is time efficiency, and the second is space efficiency. Time efficiency is called time complexity, while space efficiency is called space complexity. Time complexity mainly measures the running speed of an algorithm, while space complexity mainly measures the extra space required by an algorithm. In the early days of computer development, the storage capacity of computers was very small. So we care a lot about space complexity. However, after the rapid development of the computer industry, the storage capacity of computers has reached a very high level. So we no longer need to pay special attention to the space complexity of an algorithm.
1.2 The 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. The time it takes to execute an algorithm cannot be calculated theoretically. You can only know it if you put your program on the machine and run it. But do we need to test every algorithm on a computer? It is possible to test everything on a computer, but this is very troublesome, so the time complexity analysis method is introduced. The time an algorithm takes is proportional to the number of executions of its statements.The number of executions of basic operations in an algorithm is the time complexity of the algorithm.
1.3 The concept of space complexity
Space complexity is a measure of the amount of storage space an algorithm temporarily occupies duringrunning. Space complexity is not how many bytes of space the program occupies, because this is not very meaningful, so space complexity is calculated by the number of variables. The space complexity calculation rules are basically similar to the practical complexity, and the big O asymptotic notation is also used.
1.4 The significance of complexity calculation in algorithms
2.1 How to calculate the time complexity of common algorithms?
2.2 Big O’s asymptotic representation
// Please calculate how many times the basic operation of Func1 has been executed?
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--)
{
+ + count;
}
printf("%d\
", count);
}
Number of basic operations performed by Func1:
F(N)=N^2 + 2N + 10
N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010
In practice, when we calculate the time complexity, we do not actually have to calculate the exact number of executions, but only the approximate number of executions, so here we use the asymptotic representation of Big O.
Big O notation: It is a mathematical notation used to describe the asymptotic behavior of functions.
Derivation of the Big O-order method:
1. Replace all additive constants in the run time with constant 1.
2. In the modified running 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 term. The result is Big O order. After using Big O’s asymptotic representation, the time complexity of Func1 is:
O(N^2)
N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000
Through the above, we will find that the asymptotic representation of Big O removes those items that have little impact on the result, and expresses the number of executions concisely and clearly.
In addition, there are best, average and worst cases for the time complexity of some algorithms:
Worst case: maximum number of runs for any input size (upper bound)
Average case: expected number of runs for any input size
Best case: minimum number of runs (lower bound) for any input size
For example: Search for a data x in an array of length N
Best case: found 1 time
Worst case: Found N times
Average situation: N/2 times found
In practice, the general focus is on the worst operating situation of the algorithm, so the time complexity of searching for data in the array is O(N)
2.3 Common time complexity calculation examples
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--)
{
+ + count;
}
printf("%d\
", count);
}
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;
}
printf("%d\
", count);
}
Example 3:
// Calculate the time complexity of Func4?
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; + + k)
{
+ + count;
}
printf("%d\
", count);
}
Example 4:
//The time complexity of calculating strchr?
const char* strchr(const char* str, char character)
{
while (*str != '\0')
{
if (*str == character)
return str;
+ + str;
}
return NULL;
}
Example 5:
// Calculate the time complexity of BubbleSort?
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; + + i)
{
if (a[i - 1] > a[i])
{
Swap( & amp;a[i - 1], & amp;a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
Example 6:
// Calculate the time complexity of BinarySearch?
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n;
while (begin < end)
{
int mid = begin + ((end - begin) >> 1);
if (a[mid] < x)
begin = mid + 1;
else if (a[mid] > x)
end = mid;
else
return mid;
}
return -1;
}
Example 7:
//The time complexity of calculating factorial recursion Factorial?
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N - 1) * N;
}
Example answers and analysis:
1. The basic operation of Example 1 was executed 2N + 10 times. By deriving the big O-order method, we know that the time complexity is O(N)
2. The basic operation of Example 2 is executed M + N times, there are two unknowns M and N, and the time complexity is O(N + M)
3. The basic operation of Example 3 was executed 10 times. By deriving the big O-order method, the time complexity is O(1)
4. In Example 4, the basic operation can be executed once at best and N times at worst. The time complexity is generally at worst, and the time complexity is O(N).
5. The basic operation of Example 5 is executed N times at best and (N*(N + 1)/2 times at worst. By deriving the big O-order method + time complexity, the worst time complexity is generally O(N). ^2)
6. The basic operation of Example 6 is performed once at best and O(logN) times at worst. The time complexity is O(logN) ps: logN means that the base is 2 and the logarithm is N in algorithm analysis. In some places it will be written lgN. (It is recommended to explain how logN is calculated through origami search)
7. Example 7 found through calculation and analysis that the basic operation is recursive N times, and the time complexity is O(N).
Complexity comparison:
2.2. Common space complexity calculations
Space complexity is a measure of the amount of storage space an algorithm temporarily occupies during its operation. Space complexity is not how many bytes of space the program occupies, because this is not very meaningful, so space complexity is calculated by the number of variables. The space complexity calculation rules are basically similar to the practical complexity, and the Big O asymptotic notation is also used.
Example 1:
// Calculate the space complexity of BubbleSort?
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; + + i)
{
if (a[i - 1] > a[i])
{
Swap( & amp;a[i - 1], & amp;a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
Example 2:
// Calculate the space complexity of Fibonacci?
long long* Fibonacci(size_t n)
{
if(n==0)
return NULL;
long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
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:
// Calculate the space complexity of factorial recursion Factorial?
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}
Example answers and analysis:
1. Example 1 uses a constant amount of extra space, so the space complexity is O(1)
2. Example 2 dynamically opens up N spaces, and the space complexity is O(N)
3. Example 3 is called recursively N times, opening up N stack frames, and each stack frame uses a constant amount of space. The space complexity is O(N)
3. Algorithm question exercises with complexity requirements
3.1 Disappearing Numbers OJ Link: Interview Question 17.04. Disappearing Numbers – LeetCode
3.2 Rotating array OJ link: 189. Rotating array – LeetCode
