The complexity of the algorithm
Preamble
As a programmer, you've probably heard more or less the term "complexity of the algorithm". Many people believe that the complexity of the algorithm represents a fast or slow running time of a program, but is this a right concept? The following article will give you an overview of the complexity of an algorithm.
Why need to measure the complexity of the algorithm
Usually when solving a problem, we can come up with different algorithms but will have to choose the best algorithm. Normally, we will base on the following criteria:
- Correct algorithm.
- Simple algorithm.
- Algorithms performed quickly.
To check the correctness of an algorithm, we will often have to try it with a certain data set and compare the results obtained with known results. However, this is not certain because this algorithm may be true for this data set but not for another data set. The correctness of an algorithm needs to be proved by math, temporarily we don't mention it here.
For programs that use only a few times, the simple algorithm request takes precedence because we need an easy-to-understand and easy-to-install algorithm, which does not raise the runtime issue because we only run A few times.
However, when a program is used repeatedly, time-saving requests will be particularly prioritized. However, the execution time of the program depends on many factors such as computer configuration, language used, compiler, input data, etc. Therefore, when comparing 2 algorithms were implement, not sure if the program runs faster has better algorithms. The "complexity of the algorithm" was born to solve this problem.
How to calculate the complexity of the algorithm
The complexity of an algorithm is a function depending on the magnitude of the input data. See if an object is in the list of N elements, sorting up the sequence of numbers including N numbers, … N at This is the size of the input data
In order to estimate the complexity of an algorithm, people often use the concept of O-scale and Theta (Θ).
1. Big O
Here we use a general quantity of resources to use R (n). It can be the number of calculations (can count the number of memory accesses, or write to memory); but it can also be the program execution time (time complexity) or the amount of memory required to run the program (spatial complexity).
1.1 Definition:
Suppose f (n) and g (n) are non-negative real functions of non-negative integer arguments. We say "g (n) is O of f (n)" and write as: g (n) = O (f (n)) if there are positive constants C and n0 such that g (n) <= C * f (n) for all n> = n0
1.2 Calculation method:
Computational complexity of algorithm: O (f (n))
• Determining the computational complexity of the algorithm in practice can be calculated by some simple rules:
– Rules to remove constants:
1 | T (n) = O (cf (n)) = O (f (n)) where c is a positive constant |
– Rule to get max:
1 | T (n) = O (f (n) + g (n)) = O (max (f (n), g (n))) |
– Rules of addition:
1 2 3 | T1 (n) = O (f (n)) T2 (n) = O (g (n)) T1 (n) + T2 (n) = O (f (n) + g (n)) |
– Multiplication rules:
1 2 3 | Program segment has execution time T (n) = O (f (n)) If you execute k (n) times the program segment with k (n) = O (g (n)) then the complexity will be O (g (n) .f (n)) |
1.3 Example:
Example 1:
1 | s = n * (n-1) / 2; |
In the above example, the algorithm's complexity is O (1)
Example 2:
1 2 3 4 5 6 7 | s = 0; // O (1) for (i = 0; i <= n; i ++) { p = 1; // O (1) for (j = 1; j <= i; j ++) p = p * x / j; // O (1) s = s + p; // O (1) } |
The number of operations performed p = p * x / j is n (n-1) / 2
=> The complexity of this code is O (1) + O (1) + O (n (n-1) / 2) + O (1) + O (1) = O (n2)
Example 3:
1 2 3 4 5 6 7 8 | for (i = 1; i <= n; i ++) { for (u = 1; u <= m; u ++) for (v = 1; v <= n; v ++) // command for j: = 1 to x do for k: = 1 to z do // command } |
=> The complexity of this algorithm is: O (n max (n m, x * z))
Theta and Omega
Similar to Big O, if the constants C, k1, k2 are found to be positive, independent of n, so that with sufficient numbers, the functions R (n), f (n) and h ( n) are positive and R (n)> = Cf (n) and k1.h (n) = <R (n) <= k2.h (n), then we say the algorithm has a greater complexity than Omega ( f (n)) and true by the size of Theta (h (n))
We can understand Big (O), Omega, and Theta as the implicit functions of the algorithm's complexity calculation function.
Conclude
The above article gives an overview of the complexity of the algorithm. That not only represents a fast / slow runtime of a program but it represents the system dynamics when the input size increases.
Hopefully after this article, every time you put a hand in writing a certain program, consider and calculate the program section to have complexity in the allowable level.
Thank you for taking the time to read the article.