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

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

logarithmic order

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

Linear order O(n)

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)

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

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!