Example tutorial on python algorithm representation concept literacy

This article mainly introduces the concept literacy tutorial of python algorithm representation to everyone in detail. It has certain reference value. Interested friends can refer to it.

This article explains the concept of python algorithm representation for everyone. For your reference, the specific content is as follows

Constant order O(1)

Constant is also called a fixed number, which refers to a constant whose value does not change. The opposite is Variable

Why is the time complexity of the following algorithm not O(3), but O(1).

int sum = 0,n = 100; /*执行一次*/ 
sum = （1+n）*n/2; /*执行一次*/ 
printf（"%d", sum）; /*行次*/

The number of runs function of this algorithm is f(n)=3. According to our method of deriving the big O order, the first step is to change the constant term 3 to 1. When retaining the highest-order term, we found that it has no highest-order term at all, so the time complexity of this algorithm is O(1).

In addition, let us imagine that if the statement sum=(1+n)*n/2 in this algorithm has 10 sentences, that is:

int sum = 0, n = 100; /*执行1次*/ 
sum = （1+n）*n/2; /*执行第1次*/ 
sum = （1+n）*n/2; /*执行第2次*/ 
sum = （1+n）*n/2; /*执行第3次*/ 
sum = （1+n）*n/2; /*执行第4次*/ 
sum = （1+n）*n/2; /*执行第5次*/ 
sum = （1+n）*n/2; /*执行第6次*/ 
sum = （1+n）*n/2; /*执行第7次*/ 
sum = （1+n）*n/2; /*执行第8次*/ 
sum = （1+n）*n/2; /*执行第9次*/ 
sum = （1+n）*n/2; /*执行第10次*/ 
printf（"%d",sum）; /*执行1次*/

In fact, no matter what n is, the above The two pieces of code are the difference between 3 and 12 executions. This algorithm, which has a constant execution time regardless of the size of the problem (the size of n), is called a time complexity of O(1), and is also called a constant order.

Note: No matter what the constant is, we will record it as O(1), not any other number such as O(3), O(12), etc. This is a mistake often made by beginners.

Derivation of the Big O method

1. Replace all additive constants in the running time with constant 1

2. In the modified number of runs function, only the highest-order term

3 is retained. If the highest-order term exists and is not 1, the constant multiplied by this term

is removed Logarithm of order O(log2n)

##Logarithm

If the x power of a is equal to N (a>0, and a is not equal to 1), then the number x is called the logarithm of N with a as the base (logarithm), recorded as x=logaN, . Among them, a is called the base of the logarithm, and N is called the real number.

5^2 = 25, recorded as 2= log5 25
Logarithm is an operation, and exponential is a reciprocal operation. For example

① 3^2=9 <==> 2=log<3>9;

② 4^(3/2)=8 <==> 3 /2=log<4>8;

③ 10^n=35 <==> n=lg35. For ease of use, people gradually record common logarithms with base 10 as lgN

logarithmic order

int count = 1; 
while (count < n) 
{  
count = count * 2; /* 时间复杂度为O(1)的程序步骤序列 */ 
}

Since each count After multiplying by 2, it is one point closer to n.

In other words, how many 2s multiplied together are greater than n, then the loop will exit.

Get x=log2n from 2^x=n. So the time complexity of this loop is O(logn).

Linear order O(n)

The execution time increases proportionally with the size of the problem

data = [ 8,3,67,77,78,22,6,3,88,21,2]
find_num = 22
for i in data:
  if i == 22:
    print("find",find_num,i )

Linear logarithmic order O(nlog2n )

square order O(n^2)

for i in range(100):
 
  for k in range(100):
    print(i,k)

cubic order O(n^3)

k times Square order O(n^k),
exponential order O(2^n).

As the problem size n continues to increase, the above time complexity continues to increase, and the execution efficiency of the algorithm becomes lower.​

The above is the detailed content of Example tutorial on python algorithm representation concept literacy. For more information, please follow other related articles on the PHP Chinese website!