search
HomeBackend DevelopmentPython TutorialExample 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=log9;

② 4^(3/2)=8 3 /2=log8;

③ 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!

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
What is Python Switch Statement?What is Python Switch Statement?Apr 30, 2025 pm 02:08 PM

The article discusses Python's new "match" statement introduced in version 3.10, which serves as an equivalent to switch statements in other languages. It enhances code readability and offers performance benefits over traditional if-elif-el

What are Exception Groups in Python?What are Exception Groups in Python?Apr 30, 2025 pm 02:07 PM

Exception Groups in Python 3.11 allow handling multiple exceptions simultaneously, improving error management in concurrent scenarios and complex operations.

What are Function Annotations in Python?What are Function Annotations in Python?Apr 30, 2025 pm 02:06 PM

Function annotations in Python add metadata to functions for type checking, documentation, and IDE support. They enhance code readability, maintenance, and are crucial in API development, data science, and library creation.

What are unit tests in Python?What are unit tests in Python?Apr 30, 2025 pm 02:05 PM

The article discusses unit tests in Python, their benefits, and how to write them effectively. It highlights tools like unittest and pytest for testing.

What are Access Specifiers in Python?What are Access Specifiers in Python?Apr 30, 2025 pm 02:03 PM

Article discusses access specifiers in Python, which use naming conventions to indicate visibility of class members, rather than strict enforcement.

What is __init__() in Python and how does self play a role in it?What is __init__() in Python and how does self play a role in it?Apr 30, 2025 pm 02:02 PM

Article discusses Python's \_\_init\_\_() method and self's role in initializing object attributes. Other class methods and inheritance's impact on \_\_init\_\_() are also covered.

What is the difference between @classmethod, @staticmethod and instance methods in Python?What is the difference between @classmethod, @staticmethod and instance methods in Python?Apr 30, 2025 pm 02:01 PM

The article discusses the differences between @classmethod, @staticmethod, and instance methods in Python, detailing their properties, use cases, and benefits. It explains how to choose the right method type based on the required functionality and da

How do you append elements to a Python array?How do you append elements to a Python array?Apr 30, 2025 am 12:19 AM

InPython,youappendelementstoalistusingtheappend()method.1)Useappend()forsingleelements:my_list.append(4).2)Useextend()or =formultipleelements:my_list.extend(another_list)ormy_list =[4,5,6].3)Useinsert()forspecificpositions:my_list.insert(1,5).Beaware

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

SublimeText3 Linux new version

SublimeText3 Linux new version

SublimeText3 Linux latest version

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools