Read the algorithm in the data structure

I. Introduction

Second, the general method of algorithm analysis

Before introducing the time-space complexity analysis method of the algorithm, we first introduce how to quantify the actual running performance of the algorithm. Here we select the quantitative indicator of the performance of the measurement algorithm is its actual running time. Usually this run time is related to the size of the problem to be solved by the algorithm. For example, the time to sort 1 million is usually longer than the time to sort 100,000. Therefore, when we observe the running time of the algorithm, we must also consider the scale of the problem it solves, and observe how the actual running time of the algorithm grows as the size of the problem grows. Here we use the example in the algorithm (4th edition) (Douban) , the code is as follows:

The two classes StdIn and StdOut used in the above code are here:

https://github.com/absfree/Algo. We can see that the function of the above code is to count the number of all three integer tuples in the int[] array and 0. The algorithm used is very straightforward, that is, traversing the array from the beginning, taking three numbers at a time. If the sum is 0, the count is incremented by one, and the count value returned last is the number of triples with a sum of 0. Here we take three files with integer numbers of 1000, 2000, 4000 (these files can be found in the project address above) to test the above algorithm and observe how its running time grows with the size of the problem. Changed.

A straightforward way to measure the running time of a process is to obtain the current time before and after the process is run. The difference between the two is the running time of the process. When our process itself requires a short execution time, there may be some error in this measurement method, but we can reduce it by averaging this process and then averaging it. Below we will actually measure the running time of the above algorithm, the relevant code is as follows:

We use 1000, 2000, 4000 integers as input, and the results obtained are as follows

We can see from the above results that when the scale of the problem becomes twice the original, the actual running time is about 8 times. According to this phenomenon, we can make a conjecture: the running time of the program on the problem size N is T(N) = k*(n^3).

In this relationship, when n becomes twice the original, T(N) becomes 8 times the original. So does the running time of the ThreeSum algorithm and the problem size satisfy the above functional relationship? After introducing the relevant content of the algorithm's time complexity, we will look back at this issue.

2. Analysis of time complexity of the algorithm

Regarding the time complexity of the algorithm, here we briefly introduce the three related symbolic notations:

The first type is Big O notation, which gives the "gradual upper bound" of the runtime, which is the upper limit of the algorithm's run time in the worst case. It is defined as follows: for f(n) and g(n), if there are constants c and N0 such that |f(n)| < c * g(n) for all n > N0, then f( n) is O(g(n).

The third is called Big Ω notation, which gives the "gradient lower bound" of the run time, which is the lower limit of the algorithm's run time in the worst case. It is defined as follows: for f(n) and g(n), if there are constants c and N0, such that for all n > N0, |f(n)| > c * g(n), then f( n) is Ω(g(n)).

The third type is Big Θ notation, which determines the "progressive bound" of the runtime. The definition is as follows: for f(n) and g(n), if there are constants c and N0, for all n> N0, |f(n)| = c * g(n), then f(n) is Θ is Θ (g(n)).

The most commonly used in our usual algorithm analysis is Big O notation. Below we will introduce the specific method of analyzing the time complexity of the algorithm. If the concept of Big O notation is not very well understood, I recommend you read this article: http://blog.jobbole.com/55184/.

(2) Analysis method of time complexity

In this part, we will use the above ThreeSum program as an example to introduce the analysis method of algorithm time complexity. For the convenience of reading, please post the above program here:

Before introducing the time complexity analysis method, we first determine what the running time of the algorithm depends on. Intuitively, the running time of an algorithm is the sum of time spent executing all program statements. However, in the actual analysis, we do not need to consider the running time of all the program statements, what we should do is to focus on the most time-consuming part, that is, the most frequent and time-consuming operation. That is to say, before analyzing the time complexity of a program, we must first determine which executions of the statements in this program take up most of its execution time, while those that are time-consuming but only perform constant times (and problems) Scale-independent operations can be ignored. We select the most time-consuming operation and estimate the time complexity of the algorithm by calculating the number of executions of these operations. Let's take a closer look at this process.

First we see that the first and second lines of the above code will only be executed once, so we can ignore them. Then we see that lines 4 through 12 are a three-layer loop, and the most memory loop body contains an if statement. In other words, the if statement is the most time-consuming statement in the above code. We only need to calculate the number of executions of the if statement to estimate the time complexity of the algorithm. In the above algorithm, our problem size is N (the number of elements contained in the input array), we can also see that the number of executions of the if statement is related to N. It is not difficult to conclude that the if statement will execute N * (N - 1) * (N - 2) / 6 times, so the time complexity of this algorithm is O(n^3). This also confirms the functional relationship between our previous guess and the size of the problem (T(n) = k * n ^ 3). From this we can also know that the time complexity of the algorithm is characterized by the growth rate of the running time of the algorithm as the size of the problem grows. In normal use, Big O notation is usually not strictly the upper limit of the runtime of the worst-case algorithm, but is used to represent the upper limit of the progressive performance of the algorithm under normal circumstances, in the worst case scenario using the Big O notation description algorithm. When we run the upper limit of the time, we usually add the qualifier "worst case".

From the above analysis, we know that the time complexity of the analysis algorithm only takes two steps (a little less than putting the elephant in the refrigerator:)):

Find a statement with a large number of executions as a [key operation] that determines the running time;

Analyze the number of executions of critical operations.

In the above example, we can see that no matter what the integer array we input, the number of executions of the if statement is constant, which means that the running time of the above algorithm is independent of the input. The actual runtime of some algorithms is highly dependent on the input we give. We will introduce this issue below.

3, the expected running time of the algorithm

The expected runtime of the algorithm can be understood as the running time of the algorithm under normal circumstances. In many cases, we are more concerned with the expected runtime of the algorithm than the upper limit of the algorithm in the worst case, because the worst-case and best-case probability is lower, we are more often encountered in general . For example, although the time complexity of the quick sort algorithm and the merge sort algorithm is O(nlogn), the fast sorting is often faster than the merge sorting under the same problem scale, so the expected running time of the fast sorting algorithm is better than the merge sorting. The expected time is small. However, in the worst case, the time complexity of fast sorting will become O(n^2). The fast sorting algorithm is an algorithm whose runtime depends on the input. For this problem, we can disturb the input array to be sorted. The order to avoid the worst case.

4, magnification experiment

Let us introduce the "magnification experiment" in the book (4th edition) (Douban) . This method can easily and effectively predict the performance of the program and determine their running time is roughly an order of magnitude. Before the formal introduction of the rate experiment, let us briefly introduce the concept of “growth order” (also quoted from the book “Algorithms”):

We use ~f(N) to represent all functions that tend to be 1 as the result of dividing N by f(N). Using g(N)~f(N), g(N) / f(N) approaches 1 as the N increases. Usually the approximate method we use is g(N) ~ a * f(N). We call f(N) the order of magnitude of growth of g(N).

We still take the ThreeSum program as an example, assuming g(N) represents the number of times the if statement is executed when the input array size is N. According to the above definition, we can get g(N) ~ N ^ 3 (when N tends to positive infinity, g(N) / N^3 approaches 1). Therefore, the growth order of g(N) is N^3, that is, the increase of the running time of the ThreeSum algorithm is N^3.

Now, let's formally introduce the rate experiment (the following content mainly refers to the book "Algorithm" mentioned above, combined with some personal understanding). First we have a small program to warm up:

The above code will start with 250. The size of the problem with ThreeSum is doubled each time, and the size of the problem and the corresponding running time are output after each run of ThreeSum. The output from running the above program is as follows:

The reason why the above output differs from the theoretical value is because the actual operating environment is complex and variable, and thus many deviations are generated. The way to minimize this deviation is to run the above program multiple times and take the average. With the warm-up small program above, we can formally introduce this method, which can easily and effectively predict the performance of any program and judge the running time of its approximate growth. In fact, its work is based on the above. The DoublingTest program, the general process is as follows:

Develop an [input generator] to produce the various possible inputs in real-world situations.

Run the following DoublingRatio program repeatedly until the value of time/prev approaches the limit 2^b, then the algorithm grows by about N^b (b is a constant).

The DoublingRatio program is as follows:

Run the magnification program, we can get the following output:

We can see that time/prev does converge to 8 (2^3). So why do you run the program repeatedly by doubling the input, and the proportion of runtime will tend to be a constant? The answer is the following [magnification theorem]:

If T(N) ~ a * N^b * lgN, then T(2N) / T(N) ~2^b.

The proof of the above theorem is very simple. It is only necessary to calculate the limit of T(2N) / T(N) when N tends to positive infinity. Among them, "a * N^b * lgN" basically covers the growth magnitude of common algorithms (a, b are constant). It is worth noting that when an algorithm's growth level is NlogN, it is tested for rate, and we will get its running time to increase by about N. In fact, this is not contradictory, because we can't speculate that the algorithm conforms to a specific mathematical model based on the results of the multiplication experiment. We can only roughly predict the performance of the corresponding algorithm (when N is between 16000 and 32000, 14N and NlgN is very close).

5. Equalization analysis

Consider the ResizingArrayStack that we mentioned earlier in the in-depth understanding of the data structure's linked list, that is, the underlying array that supports dynamic resizing. Each time we add an element to the stack, we will determine whether the current element is filled with an array. If it is filled, create a new array twice the size and copy all the elements from the original array to the new array. . We know that the complexity of the push operation is O(1) when the array is not filled, and when a push operation fills the array, creating a new array and copying will make the complexity of the push operation suddenly. Rise to O(n).

For the above case, we obviously can't say that the complexity of push is O(n). We usually think that the "average complexity" of push is O(1), because after every n push operations, it will trigger a "copy element". To the new array, so the n pushes spread the cost equally. For each of the series of pushes, their equalization cost is O(1). This method of recording the total cost of all operations and dividing the cost by the total number of operations is called equalization analysis (also called amortization analysis).

Third, the small test of the knife and the actual combat name interview questions

Earlier we introduced some of the postures of algorithm analysis, so now we will apply what we have learned to solve the interview/pen test questions about algorithm analysis in several first-line Internet companies.

[Tencent] The time complexity of the algorithm below is ____

Int foo(int n) {

If (n <= 1) {

Return 1;

}

Return n * foo(n - 1);

}

After seeing this question, we need to analyze the time complexity of the algorithm. The first step we need to make is to determine the key operation. The key operation here is obviously the if statement, then we only need to judge the number of times the if statement is executed. First we see that this is a recursive process: foo will continuously call itself until foo's argument is less than or equal to 1, foo will return 1, and then the if statement will not be executed. From this we can know that the number of times the if statement is called is n times, so the time complexity is O(n).

[Jingdong] The time complexity of the following function is ____

Void recursive(int n, int m, int o) {

If (n <= 0) {

Printf("%d, %d", m, o);

} else {

Recursive(n - 1, m + 1, o);

Recursive(n - 1, m, o + 1);

}

}

This question is obviously more difficult than the previous question, so let's solve it step by step. First of all, its key operation is the if statement, so we only need to determine the number of executions of the if statement. The above function will recursively call itself when n > 0. What we need to do is to determine how many if statements have been executed before the recursive base case (ie, n <= 0) is reached. Let us assume that the number of executions of the if statement is T(n, m, o), then we can get further: T(n, m, o) = T(n-1, m+1, o) + T(n-1 , m, o+1) (when n > 0). We can see that the base case has nothing to do with the parameters m, o, so we can further simplify the above expression to T(n) = 2T(n-1), from which we can get T(n) = 2T(n-1 ) = (2^2) * T(n-2)...so we can get the time complexity of the above algorithm as O(2^n).

[Jingdong] The time complexity of the following program is ____ (where m > 1, e > 0)

x = m;

y = 1;

While (x - y > e) {

x = (x + y) / 2;

y = m / x;

}

Print(x);

The key operation of the above algorithm is the two assignment statements in the while statement. We only need to calculate the number of executions of these two statements. We can see that when x - y > e, the statement inside the while statement will execute, and x = (x + y) / 2 makes x smaller and smaller (when y<

[Sogou] Suppose the calculation time of an algorithm can be expressed by the recursion relation T(n) = 2T(n/2) + n, T(1) = 1, then the time complexity of the algorithm is ____

According to the recursion relation given by the topic, we can further obtain: T(n) = 2(2T(n/4) + n/2) + n = ... will be further developed by recursion, we can get the algorithm The time complexity is O(nlogn), and the detailed process is not attached here.