没有合适的资源?快使用搜索试试~ 我知道了~
首页Python数据结构详解:从基础到高级算法实现
Python数据结构详解:从基础到高级算法实现
需积分: 10 5 下载量 46 浏览量
更新于2024-07-18
收藏 7.25MB PDF 举报
本资源是一份全面的Python数据结构教程,旨在帮助初学者和进阶开发者深入理解数据结构的基础概念、算法原理以及如何在Python 3中实现。课程内容涵盖了以下几个主要部分: 1. 入门与基础: - 介绍:明确了学习目标,即掌握数据结构和算法,为编程提供坚实基础。 - 快速开始:指导读者如何快速进入学习状态,了解计算机科学和编程的基本概念。 - 数据结构与抽象数据类型:解释了为何要学习这些概念,它们在编程中的重要性。 - Python基础回顾:确保对Python语言有扎实的理解,为后续内容打下基础。 2. 算法分析: - 算法分析的目标是理解算法效率,包括大O符号的运用。 - 通过实例(如乱序字符串检查)演示如何进行分析。 - 比较Python不同数据结构(如列表、字典)的性能特点。 3. 基本数据结构: - 线性数据结构:如栈和队列的定义及其抽象数据类型。 - 栈:讲解Python实现栈的代码示例,涉及括号匹配、符号匹配等应用。 - 队列:同样提供Python实现,如模拟烫手山芋和打印机问题。 - 双端队列(Deque):介绍其特性和Python实现,如回文检查。 4. 递归: - 递归的介绍及其在编程中的应用,如计算列表和、整数进制转换等。 - 递归三定律,以及如何利用栈帧实现递归函数。 每一段内容都围绕着具体的算法和数据结构展开,不仅理论讲解清晰,还配以实际的Python代码示例,使学习者能够直观地理解和实践。通过学习这份资料,读者将能够提升编程技巧,理解数据结构在Python中的核心作用,为以后的项目开发打下坚实的基础。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/10621137/bg10.jpg)
2.1.目标
理解算法分析的重要性
能够使用 大O 符号描述算法执行时间
理解 Python 列表和字典的常见操作的 大O 执行时间
理解 Python 数据的实现是如何影响算法分析的。
了解如何对简单的 Python 程序做基准测试( benchmark )。
2.1.目标
16
![](https://csdnimg.cn/release/download_crawler_static/10621137/bg11.jpg)
2.2.什么是算法分析
一些普遍的现象是,刚接触计算机科学的学生会将自己的程序和其他人的相比较。你可能还
注意到,这些计算机程序看起来很相似,尤其是简单的程序。经常出现一个有趣的问题。当
两个程序解决同样的问题,但看起来不同,哪一个更好呢?
为了回答这个问题,我们需要记住,程序和程序代表的底层算法之间有一个重要的区别。正
如我们在第 1 章中所说,一种算法是一个通用的,一步一步解决某种问题的指令列表。它是
用于解决一种问题的任何实例的方法,给定特定输入,产生期望的结果。另一方面,程序是
使用某种编程语言编码的算法。根据程序员和他们所使用的编程语言的不同,可能存在描述
相同算法的许多不同的程序。
要进一步探讨这种差异,请参考 ActiveCode 1 中显示的函数。这个函数解决了一个我们熟悉
的问题,计算前 n 个整数的和。该算法使用初始化值为 0 的累加器( accumulator )变量。
然后迭代 n 个整数,将每个依次添加到累加器。
ActiveCode 1
def sumOfN(n):
theSum = 0
for i in range(1,n+1):
theSum = theSum + i
return theSum
print(sumOfN(10))
现在看看 ActiveCode 2 中的函数。乍一看,它可能很奇怪,但进一步的观察,你可以看到这
个函数本质上和前一个函数在做同样的事情。不直观的原因在于编码习惯不好。我们没有使
用良好的标识符( identifier )名称来提升可读性,我们在迭代步骤中使用了一个额外的赋
值语句,这并不是真正必要的。
ActiveCode 2
def foo(tom):
fred = 0
for bill in range(1,tom+1):
barney = bill
fred = fred + barney
return fred
print(foo(10))
2.2.什么是算法分析
17
![](https://csdnimg.cn/release/download_crawler_static/10621137/bg12.jpg)
先前我们提出一个问题是哪个函数更好,答案取决于你的标准。如果你关注可读性,函数
sumOfN 肯定比 foo 好。事实上,你可能已经在介绍编程的课程中看到过很多例子,他们的目
标之一就是帮助你编写易于阅读和理解的程序。然而,在本课程中,我们对算法本身的表示
更感兴趣(当然我们希望你继续努力编写可读的,易于理解的代码)。
算法分析是基于每种算法使用的计算资源量来比较算法。我们比较两个算法,说一个比另一
个算法好的原因在于它在使用资源方面更有效率,或者仅仅使用的资源更少。从这个角度来
看,上面两个函数看起来很相似。它们都使用基本相同的算法来解决求和问题。
在这点上,重要的是要更多地考虑我们真正意义上的计算资源。有两种方法,一种是考虑算
法解决问题所需的空间或者内存。解决方案所需的空间通常由问题本身决定。但是,有时候
有的算法会有一些特殊的空间需求,这种情况下我们需要非常仔细地解释这些变动。
作为空间需求的一种替代方法,我们可以基于算法执行所需的时间来分析和比较算法。这种
测量方式有时被称为算法的“执行时间”或“运行时间”。我们可以通过基准分析( benchmark
analysis )来测量函数 SumOfN 的执行时间。这意味着我们将记录程序计算出结果所需的实
际时间。在 Python 中,我们可以通过记录相对于系统的开始时间和结束时间来对函数进行基
准测试。在 time 模块中有一个 time 函数,它可以在任意被调用的地方返回系统时钟的当前时
间(以秒为单位)。通过在开始和结束的时候分别调用两次 time 函数,然后计算差异,就可
以得到一个函数执行花费的精确秒数(大多数情况下是这样)。
Listing 1
import time
def sumOfN2(n):
start = time.time()
theSum = 0
for i in range(1,n+1):
theSum = theSum + i
end = time.time()
return theSum, end-start
Listing 1 嵌入了时间函数,函数返回一个包含了执行结果和执行消耗时间的元组
( tuple )。如果我们执行这个函数 5 次,每次计算前 10,000 个整数的和,将得到如下结
果:
2.2.什么是算法分析
18
![](https://csdnimg.cn/release/download_crawler_static/10621137/bg13.jpg)
>>>for i in range(5):
print("Sum is %d required %10.7f seconds"%sumOfN(10000))
Sum is 50005000 required 0.0018950 seconds
Sum is 50005000 required 0.0018620 seconds
Sum is 50005000 required 0.0019171 seconds
Sum is 50005000 required 0.0019162 seconds
Sum is 50005000 required 0.0019360 seconds
我们发现时间是相当一致的,执行这段代码平均需要0.0019秒。如果我们运行计算前
100,000 个整数的和的函数呢?
>>>for i in range(5):
print("Sum is %d required %10.7f seconds"%sumOfN(100000))
Sum is 5000050000 required 0.0199420 seconds
Sum is 5000050000 required 0.0180972 seconds
Sum is 5000050000 required 0.0194821 seconds
Sum is 5000050000 required 0.0178988 seconds
Sum is 5000050000 required 0.0188949 seconds
>>>
再次的,尽管时间更长,但每次运行所需的时间也是非常一致的,平均大约多10倍。 对于 n
等于 1,000,000,我们得到:
>>>for i in range(5):
print("Sum is %d required %10.7f seconds"%sumOfN(1000000))
Sum is 500000500000 required 0.1948988 seconds
Sum is 500000500000 required 0.1850290 seconds
Sum is 500000500000 required 0.1809771 seconds
Sum is 500000500000 required 0.1729250 seconds
Sum is 500000500000 required 0.1646299 seconds
>>>
在这种情况下,平均值也大约是前一次的10倍。现在考虑 ActiveCode 3,它显示了求解求和
问题的不同方法。函数 sumOfN3 利用封闭方程而不是迭代来计算前n个整数的和。
ActiveCode 3
def sumOfN3(n):
return (n*(n+1))/2
print(sumOfN3(10))
2.2.什么是算法分析
19
![](https://csdnimg.cn/release/download_crawler_static/10621137/bg14.jpg)
如果我们对 sumOfN3 做同样的基准测试,使用 5 个不同的 n (10,000, 100,000, 1,000,000,
10,000,000 和 100,000,000) , 我们得到如下结果
Sum is 50005000 required 0.00000095 seconds
Sum is 5000050000 required 0.00000191 seconds
Sum is 500000500000 required 0.00000095 seconds
Sum is 50000005000000 required 0.00000095 seconds
Sum is 5000000050000000 required 0.00000119 seconds
在这个输出中有两件事需要重点关注,首先上面记录的执行时间比之前任何例子都短,另外
他们的执行时间和 n 无关,看起来 sumOfN3 几乎不受 n 的影响。
但是这个基准测试能告诉我们什么?我们可以很直观地看到使用了迭代的解决方案需要做更
多的工作,因为一些程序步骤被重复执行。这可能是它需要更长时间的原因。此外,迭代方
案执行所需时间随着 n 递增。另外还有个问题,如果我们在不同计算机上或者使用不用的编
程语言运行这个函数,我们也可能得到不同的结果。如果使用老旧的计算机,可能需要更长
时间才能执行完 sumOfN3。
我们需要一个更好的方法来描述这些算法的执行时间。基准测试计算的是程序执行的实际时
间。它并不真正地提供给我们一个有用的度量( measurement ),因为它取决于特定的机器,
程序,时间,编译器和编程语言。 相反,我们希望有一个独立于所使用的程序或计算机的度
量。这个度量将有助于独立地判断算法,并且可以用于比较不同实现方法的算法的效率。
2.2.什么是算法分析
20
剩余310页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/9b816bf0c64e4c4883a84d3b60e2aa38_weixin_41362649.jpg!1)
BUPT-WT
- 粉丝: 365
- 资源: 18
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 新型矿用本安直流稳压电源设计:双重保护电路
- 煤矿掘进工作面安全因素研究:结构方程模型
- 利用同位素位移探测原子内部新型力
- 钻锚机钻臂动力学仿真分析与优化
- 钻孔成像技术在巷道松动圈检测与支护设计中的应用
- 极化与非极化ep碰撞中J/ψ的Sivers与cos2φ效应:理论分析与COMPASS验证
- 新疆矿区1200m深孔钻探关键技术与实践
- 建筑行业事故预防:综合动态事故致因理论的应用
- 北斗卫星监测系统在电网塔形实时监控中的应用
- 煤层气羽状水平井数值模拟:交替隐式算法的应用
- 开放字符串T对偶与双空间坐标变换
- 煤矿瓦斯抽采半径测定新方法——瓦斯储量法
- 大倾角大采高工作面设备稳定与安全控制关键技术
- 超标违规背景下的热波动影响分析
- 中国煤矿选煤设计进展与挑战:历史、现状与未来发展
- 反演技术与RBF神经网络在移动机器人控制中的应用
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)