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

Editor to share with you the example analysis of python data structure algorithm, I believe that most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to know it!

1. Definition of algorithm analysis

There is a question: when two seemingly different programs solve the same problem, will there be pros and cons? The answer is yes. Algorithm analysis is concerned with the comparison algorithm based on the computing resources used. We say that algorithm An is better than algorithm B because algorithm A has higher resource utilization or uses fewer resources. From this point of view, the above two functions are actually similar, and they essentially use the same algorithm to solve the accumulation problem.

What exactly does computing resource mean? It is important to think about this problem. There are two ways of thinking.

One is to consider the space or memory occupied by the algorithm when solving the problem. The total amount of space required by the solution is generally determined by the problem instance itself, but algorithms often have specific space requirements.

The second is to analyze and compare according to the time required for the implementation of the algorithm. This indicator is sometimes called the execution time or run time of the algorithm. One way to weigh the execution time of the sumOfN function is to do a benchmark analysis. In other words, we will record the actual time taken by the program to calculate the results. In Python, we record the start and end times of the function in terms of the system in which it is located. There is a time function in the time module that returns the current system clock time from the specified time point in seconds. Call this function once at the beginning and the end, calculate the difference, and you can get the execution time in seconds.

For example: we need to solve the sum of the first n numbers and judge the efficiency by calculating the time required. (use the time function here and calculate it 5 times to see how much time it takes.)

The first method: circular scheme

Import timedef sumOfN2 (n): start=time.time () thesum=0 for i in range (1): thesum=thesum+i end=time.time () return thesum,end-start# cycle 5 times for i in range (5): print ("Sum is% d required .7f seconds"% sumOfN2 (10000))

The results are as follows:

The second method: formula method

# directly use the summation formula def sumOfN3 (n): start=time.time () thesum= (1cm n) * n end=time.time () return thesum,end-startfor i in range (5): print ("Sum is% d required .7f seconds"% sumOfN3 (10000))

The results are as follows:

Intuitively, the loop scheme seems to be more demanding because some of the steps are repetitive. This seems to be the reason why it takes longer. Moreover, the time-consuming of the cyclic scheme increases with n. However, there is a problem. If you run this function on another computer, or implement it in another programming language, you are likely to get different results. If the computer were older, sumOfN3 would take even longer to execute.

We need a better way to describe the execution time of the algorithm. The benchmark calculates the actual time it takes to execute the algorithm. This is not a useful indicator because it depends on specific computers, programs, time, compilers, and programming languages. We hope to find an indicator independent of the program or computer. Such indicators will be more useful in evaluating algorithms and can be used to compare algorithms under different implementations.

two。 Big O notation

Here, in order to let you know the growth rate of some functions, I decided to list some functions.

Example: calculate the number of steps of the following program, and the order of magnitude O

A = 5b = 6c = 10for i in range (n): for j in range (n): X = I * I y = j * j z = I * j for k in range (n): W = a * k + 45 v = b * bd = 33

The number of assignments for this program is:

You can do the math for yourself.

3. Big O notation of different algorithms

Here we use different algorithms to achieve a classic out-of-order word detection question, the so-called out-of-order words are composed of the same letters, but in different order, such as heart and earth,python and typhon. To simplify the problem, let's assume that the two word strings to be tested are already the same length.

3.1 inventory method

The main purpose of this method is to count each character of the first string to see if they all appear in the second string. If so, then the two strings must be disordered words. Inventory is achieved by replacing characters with a special value in Python, None. However, because the string in Python is immutable, you first convert the second string into a list. Check each character in the first string in the character list and replace it if it is found.

Def anagramSolution1 (S1 S2): alist = list (S2) pos1=0 stillOK = True while pos1 < len (S1) and stillOK: pos2 = 0 found = False while pos2 < len (alist) and not found: if S1 [pos1] = = alist [pos2]: found = True else: pos2 = pos2 + 1 if found: Alist [pos2] = None else: stillOK = False pos1 = pos1 + 1 return stillOK

To analyze the algorithm. Note that for the n characters in S1, traverse the n characters in S2 when checking each one. To match a character in S1, all the n positions in the list are accessed once. Therefore, the number of visits is the sum of integers from 1 to n. This can be expressed by the following formula.

Therefore, the time complexity of this method is

3.2 sorting method

Although S1 and S2 are different strings, they are disordered words as long as they are made up of the same characters. Based on this, another option can be adopted. If the characters are sorted alphabetically, the result of the out-of-order words will be the same string.

Def anagramSolution2 (S1, S2): alist1 = list (S1) alist2 = list (S2) alist1.sort () alist2.sort () pos=0 matches = True while pos < len (S1) and matches: if alist1 [pos] = alist2 [pos]: pos= pos + 1 else: matches = False return matches

At first glance, you might think that the time complexity of this algorithm is O (n), because you only need to traverse it once after sorting to compare n characters. However, calling the sort method twice is not without cost. As we will see later, the inter-temporal complexity of sorting is basically O (N2) or O (nlogn), so the sorting operation plays a leading role. In other words, the algorithm is of the same order of magnitude as the sorting process.

3.3 brute force method

The way to solve the problem with brute force is basically to exhaust all possibilities. As far as out-of-order word detection is concerned, you can use the characters in S1 to generate all possible strings to see if S2 is among them. But there is a difficulty with this method. When using the characters in S1 to generate all possible strings, there are n possibilities for the 1st character, 1 possibility for the 2nd character, 2 possibilities for the 3rd character, and so on. The total number of strings is n ∗ (n − 1) ∗ (n − 2) ∗. . . . . . ∗ 3 ∗ 2 ∗ 1n * (n − 1) * (n ∗ 2) *. * 3 times 2 times 1n ∗ (n − 1) ∗ (n − 2) ∗. ∗ 3 ∗ 2 ∗ 1, that is, n! N!n! Maybe some strings will repeat, but the program can't foresee it, so it will definitely generate n! N!n! A string.

When n is larger, n! It is growing faster than 2n. In fact, if S1 has 20 characters, the number of strings is 20 characters = 2432902008176640000. Assuming one per second, it takes 77146816596 to process the entire list. This is not a good plan.

3.4 counting method

The last scheme is based on the fact that two out-of-order words have the same number of a, the same number of b, the same number of c, and so on. To determine whether two strings are out-of-order words, first count the number of times each character appears. Because there may be 26 characters, 26 counters are used for each character. Each time a character is encountered, the corresponding counter is incremented by 1. Finally, if the two counter lists are the same, then the two strings must be disordered words.

Def anagramSolution4 (S1 S2): C1 = [0] * 26 c2 = [0] * 26 for i in range (len (S1)): pos = ord (S1 [I])-ord ('a') C1 [pos] = C1 [pos] + 1 for i in range (len (S2): pos = ord (S2 [I])-ord ('a') c2 [pos] = c2 [pos] + 1 juni0 stillOK = True while j < 26 and stillOK: if C1 [j] = = c2 [j]: j=j+1 else: stillOK = False return stillOK

This scheme also has a cycle. But unlike scenario 1, the loops in this scenario are not nested. The first two counting cycles are n-order. The third loop compares two lists and loops 26 times because there may be 26 characters. All together, the total number of steps T (n) = 2n-26, that is, O (n). We find a linear order algorithm to solve the problem of out-of-order word detection.

4. Complexity of list and dictionary operations

4.1 list

4.2 Dictionary

The above is all the contents of the article "sample Analysis of python data structure algorithms". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

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.