Shulou(Shulou.com)05/31 Report--

Today, the editor will share with you the relevant knowledge points about the case analysis of time complexity and space complexity of the C language. The content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article, let's take a look at it.

1. Time complexity:

First of all, why did this concept come into being?

It turns out that in the algorithm analysis, the total number of sentence execution T (n) is a function of the problem size n, and then analyze the change of T (n) with n and determine the order of magnitude of T (n). The time complexity of the algorithm, that is, the time measure of the algorithm, is recorded as T (n) = O (f (n)). It means that with the increase of the problem size n, the growth rate of the algorithm execution time is the same as that of f (n), which is called the asymptotic time complexity of the algorithm, or time complexity for short, where f (n) is a function of the problem size n.

The notation that uses uppercase O () to reflect the time complexity of the algorithm is called Big O notation.

You can simply think of it this way: the time complexity of the algorithm is actually the number of times the basic operation is performed.

At this point, let's first talk about how to derive the large O-order method.

(1) replace all addition constants in run time with the constant 1.

(2) in the modified number of runs function, only the highest order term is retained.

(3) if the highest order term exists and its coefficient is not 1, the coefficient multiplied by this term is removed.

The result is a large O-order.

This is like a game strategy, we get a universal formula to deduce the time complexity of the algorithm. But in fact, it is not so simple to analyze the time complexity of an algorithm.

According to the definition of algorithm time complexity, we take the unofficial name, constant order O (1), logarithmic order O (log2n), linear order O (n), linear logarithmic order O (nlog2n), square order O (N2), cubic order O (n3),..., k power O (nk), exponential order O (2n). With the continuous increase of the problem size n, the above time complexity increases, and the execution efficiency of the algorithm is lower. Let's analyze and analyze it.

1. Constant order

Let's just give a few lines of code.

Int sum = 0mam n = 100th sum = (1cm n) * n hand 2x position printf ("% d", sum)

Answer aloud whether the time complexity of this algorithm is O (3) or O (1), the answer must be O (1). First of all, the function of the number of times of execution of this algorithm is f (n) = 3; according to our method of deducing a large O order, change 3 to 1, this is a constant term, there is no other term, so it is O (1). In fact, no matter what n is, this kind of algorithm with constant execution time independent of the size of the problem is called O (1) time complexity, also known as constant order.

Note: no matter what this constant is, we write it down as O (1) instead of O (3), O (5) and other numbers, which is a common mistake made by beginners.

two。 Linear order

The cyclic structure of the linear order will be much more complicated. To determine the order of an algorithm, we need to determine the number of times a particular statement is run.

In the following code, the time complexity of the loop is O (n), because the code in the loop body needs to be executed n times.

Int iBoth for

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.