Python中顺序表算法复杂度的相关知识介绍

酷敏同学_4827

酷敏同学_4827

2018-10-29

3384人浏览

转载

本篇文章给大家带来的内容是关于Python中顺序表算法复杂度的相关知识介绍,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

一.算法复杂度的引入

对于算法的时间和空间性质,最重要的是其量级和趋势,所以衡量其复杂度的函数常量因子可以忽略不计.

大O记法通常是某一算法的渐进时间复杂度,常用的渐进复杂度函数复杂度比较如下:

O(1)<o><p>

	</p>
<p>
	</p>
<p>引入时间复杂度的例子,请比较两段代码的例子,看其计算的结果	</p>
<pre class="brush:php;toolbar:false;">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("完成")

如何计算时间复杂度:

# 时间复杂度计算
# 1.基本步骤,基本操作,复杂度是O(1)
# 2.顺序结构,按加法计算
# 3.循环,按照乘法
# 4.分支结构采用其中最大值
# 5.计算复杂度,只看最高次项,例如n^2+2的复杂度是O(n^2)

二.顺序表的时间复杂度

列表时间复杂度的测试

# 测试
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))

输出结果

Python健壮编程
Python健壮编程

编写可靠Python代码,避免可变默认值、导入陷阱与运行时意外

下载

列表中方法的复杂度:

# 列表方法中复杂度
# 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为列表的长度

字典中方法的复杂度(补充)

# 字典中的复杂度
# copy O(n)
# get item O(1)
# set item O(1) 设置
# delete item O(1)
# contains(in) O(1) 字典不用遍历,所以可以一次找到
# iteration O(n)

 三.顺序表的数据结构

  1. 一个顺序表的完整信息包括两部分,一部分是表中的元素集合,另一部分是为实现正确操作而需要记录的信息这部分信息主要包括元素存储区的容量和当前表中已有的元素个数两项。

  2. 表头和数据区的组合:一体式结构:表头信息(记录容量和已有元素个数的信息)和数据区做连续储存

  3. 分离式结构:表头信息和数据区并不是连续存储的,会多处一部分信息用来存储地址单元,用来指向真实的数据区

  4. 两者差别和优劣:

# 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),采用的是分离式的存储区,动态顺序表

四. python中变量空间扩充的策略

1.在建立空表(或很小的表)时,系统分配的是一块能容纳8个元素的存储区
2.在执行插入操作(insert,append)时,如果元素存储区满就换一块四倍大的存储区
3.如果此时的表已经很大(阀值是50000),则改变政策,采用加一倍的方法。为了避免出现过多空闲的空间。

Python免费学习笔记(深入):立即使用
在学习笔记中,你将探索 Python 的核心概念和高级技巧!

相关文章

python速学教程(入门到精通)
python速学教程(入门到精通)

python怎么学习?python怎么入门?python在哪学?python怎么学才快?不用担心,这里为大家提供了python速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

python

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

20

15

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.17

20

15

GoFrame框架零基础入门
GoFrame框架零基础入门

本专题整理GoFrame框架的入门知识,从模块化设计理念、环境准备到跑通第一个Web服务,讲清目录分层、配置加载、日志与中间件的用法,并对比Gin、Go-Zero的差异,帮助Go开发者建立整体认知。

2026.11.17

20

15

SQLAlchemy 一对多关系怎么建立
SQLAlchemy 一对多关系怎么建立

SQLAlchemy 一对多关系怎么建立?本专题整理父子表外键、relationship 双向映射、关联查询、级联删除和加载优化等相关文章,帮助你理解并实现常见的 ORM 关系建模。

2026.11.17

20

10

SQLAlchemy 如何增删改查
SQLAlchemy 如何增删改查

SQLAlchemy 如何增删改查?本专题整理 ORM 新增记录、条件查询、更新和删除、Session 事务提交与批量处理等实用文章,帮助你掌握 Python 数据库操作流程。

2026.11.17

20

11

SQLAlchemy ORM 模型怎么写
SQLAlchemy ORM 模型怎么写

SQLAlchemy ORM 模型怎么写?本专题整理模型类定义、Mapped 字段映射、主键与约束、表结构创建和常见报错的相关文章,帮助你从基础配置到实际建模逐步掌握 SQLAlchemy。

2026.11.17

20

16

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

180

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

120

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

120

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程