Shulou(Shulou.com)06/03 Report--

What is the complexity of the algorithm? In view of this problem, this article introduces the corresponding analysis and answers in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible way.

Algorithm complexity: time complexity

In computer science, time complexity, also known as time complexity, the time complexity of an algorithm is a function that qualitatively describes the running time of the algorithm. This is a function that represents the length of the string input by the algorithm. Time complexity is often expressed by the big O symbol, excluding the lower order term and the first coefficient of this function. In this way, the time complexity can be called asymptotic, that is, when the size of the input value approaches infinity.

In order to calculate the time complexity, we usually estimate the number of operating units of the algorithm, and each unit runs for the same time. Therefore, the difference between the total running time and the number of operating units of the algorithm is at most a constant coefficient.

Different input values of the same size may still cause different running time of the algorithm, so we usually use the worst-case complexity of the algorithm, denoted as T (n), which is defined as the maximum running time required for any size of input n. Another less used method is the average case complexity, which is usually used only when specifically specified. The time complexity can be classified by the natural characteristics of the function T (n). For example, the algorithm with T (n) = O (n) is called "linear time algorithm", while T (n) = O (M ^ n) and M = O (T (n)), where M ≥ n > 1 is called "exponential time algorithm".

The time taken by an algorithm is directly proportional to the number of sentences executed in the algorithm, which algorithm takes more time. The number of statements executed in an algorithm is called statement frequency or time frequency. Mark it as T (n).

In general, the number of repeated basic operations in the algorithm is a function of the problem size n. If there is an auxiliary function f (n) such that when n approaches infinity and the limit value of T (n) / f (n) is a constant not equal to zero, then f (n) is said to be a function of the same order of magnitude of T (n). Write it down as T (n) = O (f (n)), and call O (f (n)) the asymptotic time complexity of the algorithm, abbreviated as time complexity.

In different algorithms, if the number of sentence execution in the algorithm is a constant, the time complexity is O (1). In addition, when the time frequency is not the same, the time complexity may be the same, such as T (n) = n2+3n+4 and T (n) = 4n2+2n+1, their frequency is different, but the time complexity is the same, all O (N2).

Time frequency

The time spent on the execution of an algorithm cannot be calculated in theory and must be tested on the computer to know. But it is impossible and unnecessary for us to test every algorithm on the computer. We just need to know which algorithm takes more time and which algorithm takes less time. And the time spent by an algorithm is directly proportional to the number of sentences executed in the algorithm, which algorithm takes more time. The number of statements executed in an algorithm is called statement frequency or time frequency. Mark it as T (n).

Space complexity

Similar to time complexity, space complexity refers to the measure of storage space required when an algorithm is executed in a computer. Recorded as:

S (n) = O (f (n))

The storage space required during the execution of the algorithm consists of three parts:

The space occupied by the algorithm program

The storage space occupied by the initial data entered

The extra space needed during the execution of the algorithm.

In many practical problems, compressed storage technology is usually used to reduce the storage space occupied by the algorithm.

The answers to the questions about the complexity of the algorithm are shared here. I hope the above content can be of some help to you. If you still have a lot of doubts to be solved, you can follow the industry information channel to learn more about it.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.