


Introduction to knowledge about the complexity of sequential list algorithms in Python
This article brings you knowledge about the complexity of sequential table algorithms in Python. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.
1. Introduction of algorithm complexity
For the time and space properties of the algorithm, the most important thing is its magnitude and trend, so the function to measure its complexity The constant factor can be ignored.
Big O notation is usually the asymptotic time complexity of a certain algorithm. The complexity of commonly used asymptotic complexity functions is compared as follows:
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
Introducing examples of time complexity, please compare the two code examples to see the calculation results
import time start_time = time.time() for a in range(0,1001): for b in range(0,1001): for c in range(0,1001): if a+b+c ==1000 and a**2 + b**2 == c**2: print("a, b, c :%d, %d, %d" % (a, b ,c)) end_time = time.time() print("times:%d" % (end_time-start_time)) print("完成")
import time start_time = time.time() for a in range(0,1001): for b in range(0,1001): c = 1000 - a - b if a**2 + b**2 == c**2: print("a, b, c :%d, %d, %d" % (a, b ,c)) end_time = time.time() print("times:%d" % (end_time-start_time)) print("完成")
How to calculate time complexity:
# 时间复杂度计算 # 1.基本步骤,基本操作,复杂度是O(1) # 2.顺序结构,按加法计算 # 3.循环,按照乘法 # 4.分支结构采用其中最大值 # 5.计算复杂度,只看最高次项,例如n^2+2的复杂度是O(n^2)
2. Time complexity of sequence list
Test of time complexity of list
# 测试 from timeit import Timer def test1(): list1 = [] for i in range(10000): list1.append(i) def test2(): list2 = [] for i in range(10000): # list2 += [i] # +=本身有优化,所以不完全等于list = list + [i] list2 = list2 + [i] def test3(): list3 = [i for i in range(10000)] def test4(): list4 = list(range(10000)) def test5(): list5 = [] for i in range(10000): list5.extend([i]) timer1 = Timer("test1()","from __main__ import test1") print("append:",timer1.timeit(1000)) timer2 = Timer("test2()","from __main__ import test2") print("+:",timer2.timeit(1000)) timer3 = Timer("test3()","from __main__ import test3") print("[i for i in range]:",timer3.timeit(1000)) timer4 = Timer("test4()","from __main__ import test4") print("list(range):",timer4.timeit(1000)) timer5 = Timer("test5()","from __main__ import test5") print("extend:",timer5.timeit(1000))
Output result
Complexity of methods in the list:
# 列表方法中复杂度 # index O(1) # append 0(1) # pop O(1) 无参数表示是从尾部向外取数 # pop(i) O(n) 从指定位置取,也就是考虑其最复杂的状况是从头开始取,n为列表的长度 # del O(n) 是一个个删除 # iteration O(n) # contain O(n) 其实就是in,也就是说需要遍历一遍 # get slice[x:y] O(K) 取切片,即K为Y-X # del slice O(n) 删除切片 # set slice O(n) 设置切片 # reverse O(n) 逆置 # concatenate O(k) 将两个列表加到一起,K为第二个列表的长度 # sort O(nlogn) 排序,和排序算法有关 # multiply O(nk) K为列表的长度
Complexity of methods in dictionary (supplementary)
# 字典中的复杂度 # copy O(n) # get item O(1) # set item O(1) 设置 # delete item O(1) # contains(in) O(1) 字典不用遍历,所以可以一次找到 # iteration O(n)
3. Data structure of sequence table
The complete information of a sequence table includes two parts, one part is the set of elements in the table, and the other part is to achieve correct operation The information that needs to be recorded mainly includes the capacity of the element storage area and the number of elements in the current table.
#Combination of header and data area: integrated structure: header information (recording capacity and number of existing elements) and data area for continuous storage
-
Separate structure: header information and data area are not stored continuously, and some information will be used to store address units to point to the real data area
The differences and advantages and disadvantages between the two:
# 1.一体式结构:数据必须整体迁移 # 2.分离式结构:在数据动态的过错中有优势
# 申请多大的空间? # 扩充政策: # 1.每次增加相同的空间,线性增长 # 特点:节省空间但操作次数多 # 2.每次扩容加倍,例如每次扩充增加一倍 # 特点:减少执行次数,用空间换效率 # 数据表的操作: # 1.增加元素: # a.尾端加入元素,时间复杂度为O(1) # b.非保序的元素插入:O(1) # c.保序的元素插入:时间度杂度O(n)(保序不改变其原有的顺序) # 2.删除元素: # a.末尾:时间复杂度:O(1) # b.非保序:O(1) # c.保序:O(n) # python中list与tuple采用了顺序表的实现技术 # list可以按照下标索引,时间度杂度O(1),采用的是分离式的存储区,动态顺序表
4. Strategies for variable space expansion in python
1. When creating an empty table (or a very small table), the system allocates a storage area that can accommodate 8 elements
2. When performing insert operations (insert, append), if the element storage area is full, replace it with a storage area of 4 Double the storage area
3. If the table is already very large (the threshold is 50000), change the policy and adopt the method of doubling the size. To avoid too much free space.
The above is the detailed content of Introduction to knowledge about the complexity of sequential list algorithms in Python. For more information, please follow other related articles on the PHP Chinese website!

Python and C each have their own advantages, and the choice should be based on project requirements. 1) Python is suitable for rapid development and data processing due to its concise syntax and dynamic typing. 2)C is suitable for high performance and system programming due to its static typing and manual memory management.

Choosing Python or C depends on project requirements: 1) If you need rapid development, data processing and prototype design, choose Python; 2) If you need high performance, low latency and close hardware control, choose C.

By investing 2 hours of Python learning every day, you can effectively improve your programming skills. 1. Learn new knowledge: read documents or watch tutorials. 2. Practice: Write code and complete exercises. 3. Review: Consolidate the content you have learned. 4. Project practice: Apply what you have learned in actual projects. Such a structured learning plan can help you systematically master Python and achieve career goals.

Methods to learn Python efficiently within two hours include: 1. Review the basic knowledge and ensure that you are familiar with Python installation and basic syntax; 2. Understand the core concepts of Python, such as variables, lists, functions, etc.; 3. Master basic and advanced usage by using examples; 4. Learn common errors and debugging techniques; 5. Apply performance optimization and best practices, such as using list comprehensions and following the PEP8 style guide.

Python is suitable for beginners and data science, and C is suitable for system programming and game development. 1. Python is simple and easy to use, suitable for data science and web development. 2.C provides high performance and control, suitable for game development and system programming. The choice should be based on project needs and personal interests.

Python is more suitable for data science and rapid development, while C is more suitable for high performance and system programming. 1. Python syntax is concise and easy to learn, suitable for data processing and scientific computing. 2.C has complex syntax but excellent performance and is often used in game development and system programming.

It is feasible to invest two hours a day to learn Python. 1. Learn new knowledge: Learn new concepts in one hour, such as lists and dictionaries. 2. Practice and exercises: Use one hour to perform programming exercises, such as writing small programs. Through reasonable planning and perseverance, you can master the core concepts of Python in a short time.

Python is easier to learn and use, while C is more powerful but complex. 1. Python syntax is concise and suitable for beginners. Dynamic typing and automatic memory management make it easy to use, but may cause runtime errors. 2.C provides low-level control and advanced features, suitable for high-performance applications, but has a high learning threshold and requires manual memory and type safety management.


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

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

Hot Article

Hot Tools

MantisBT
Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

Dreamweaver Mac version
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

PhpStorm Mac version
The latest (2018.2.1) professional PHP integrated development tool

WebStorm Mac version
Useful JavaScript development tools