This is the 21st day of my participation in Gwen Challenge
- Following up on the previous article, this one focuses on time complexity and related issues
Time complexity
Good and bad algorithms
How do you measure whether an algorithm is good or bad?
- There are many criteria to measure the quality of an algorithm, among which the two most important criteria are the time complexity and space complexity of the algorithm.
- Number of basic operations performed
- Scenario 1 T(n) = 3n, and the number of executions is linear.
- In scenario 2 T(n) = 5logn, the number of executions is logarithmically calculated.
- Scenario 3 T(n) = 2, the number of executions is constant.
- Scenario 4 T(n) = 0.5n2 + 0.5n, and the number of executions is polynomial.
Progressive time complexity
- F (n) is said to be of the same order of magnitude as T(n) if there exists a function f(n) such that the limit value of T(n)/f(n) is a constant that is not equal to zero as n approaches infinity. T(n)=O(f(n)), called O(f(n)), O is the asymptotic time complexity of the algorithm, referred to as time complexity.
- Because progressive time complexity is expressed in capital O, it is also known as the big O notation
- To put it bluntly, time complexity is the simplification of the relative execution time function of a program,T(n), to an order of magnitude, which can be n, n2, n3, etc
How do you derive time complexity? There are several principles.
- If the running time is of a constant order of magnitude, it is represented by a constant 1
- Only the highest order terms in the time function are retained
- If the highest order term exists, the coefficient in front of the highest order term is omitted
Let’s go back to the last four scenarios.
- Scenario 1
- T(n)= 3n, the highest order term is 3n and the coefficient 3 is omitted, then the time complexity of the transformation is T(n)=O(n).
- Scenario 2
- T(n) = 5logn, the highest order term is 5logn, the coefficient 5 is omitted, then the time complexity of the transformation is :T(n) =O(logn)
- Scenario 3
- T(n) = 2, only a constant order of magnitude, then the time complexity of transformation is :T(n) =O(1).
- Scenario 4
- T(n) = 0.5 N2 + 0.5 N, the highest order term is 0.5n2, the omitted coefficient is 0.5, then the time complexity of the transformation is T(n) =O(n2).