search
HomeBackend DevelopmentPython TutorialIntroduction 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

  1. 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.

  2. #Combination of header and data area: integrated structure: header information (recording capacity and number of existing elements) and data area for continuous storage

  3. 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

  4. 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!

Statement
This article is reproduced at:CSDN. If there is any infringement, please contact admin@php.cn delete
详细讲解Python之Seaborn(数据可视化)详细讲解Python之Seaborn(数据可视化)Apr 21, 2022 pm 06:08 PM

本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于Seaborn的相关问题,包括了数据可视化处理的散点图、折线图、条形图等等内容,下面一起来看一下,希望对大家有帮助。

详细了解Python进程池与进程锁详细了解Python进程池与进程锁May 10, 2022 pm 06:11 PM

本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于进程池与进程锁的相关问题,包括进程池的创建模块,进程池函数等等内容,下面一起来看一下,希望对大家有帮助。

Python自动化实践之筛选简历Python自动化实践之筛选简历Jun 07, 2022 pm 06:59 PM

本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于简历筛选的相关问题,包括了定义 ReadDoc 类用以读取 word 文件以及定义 search_word 函数用以筛选的相关内容,下面一起来看一下,希望对大家有帮助。

归纳总结Python标准库归纳总结Python标准库May 03, 2022 am 09:00 AM

本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于标准库总结的相关问题,下面一起来看一下,希望对大家有帮助。

分享10款高效的VSCode插件,总有一款能够惊艳到你!!分享10款高效的VSCode插件,总有一款能够惊艳到你!!Mar 09, 2021 am 10:15 AM

VS Code的确是一款非常热门、有强大用户基础的一款开发工具。本文给大家介绍一下10款高效、好用的插件,能够让原本单薄的VS Code如虎添翼,开发效率顿时提升到一个新的阶段。

python中文是什么意思python中文是什么意思Jun 24, 2019 pm 02:22 PM

pythn的中文意思是巨蟒、蟒蛇。1989年圣诞节期间,Guido van Rossum在家闲的没事干,为了跟朋友庆祝圣诞节,决定发明一种全新的脚本语言。他很喜欢一个肥皂剧叫Monty Python,所以便把这门语言叫做python。

Python数据类型详解之字符串、数字Python数据类型详解之字符串、数字Apr 27, 2022 pm 07:27 PM

本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于数据类型之字符串、数字的相关问题,下面一起来看一下,希望对大家有帮助。

详细介绍python的numpy模块详细介绍python的numpy模块May 19, 2022 am 11:43 AM

本篇文章给大家带来了关于Python的相关知识,其中主要介绍了关于numpy模块的相关问题,Numpy是Numerical Python extensions的缩写,字面意思是Python数值计算扩展,下面一起来看一下,希望对大家有帮助。

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

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

DVWA

DVWA

Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools

PhpStorm Mac version

PhpStorm Mac version

The latest (2018.2.1) professional PHP integrated development tool

SecLists

SecLists

SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.