数据结构与算法（Python版）第2版 课件 chap1 数据结构与算法

数据结构与算法python版

(第二版)周元哲机械工业出版社2程序设计著名计算机科学家沃思提出了一个公式：

程序=数据结构+算法。算法解决“如何操作数据？”的问题。数据结构是指定数据的类型和数据的组织形式，解决了“如何描述数据？”的问题。3程序设计过程分析问题算法与数据结构程序设计语言流程图数据结构数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。数据结构中的“关系”是指数据间的逻辑关系，与数据的物理存储方式无关，同一种逻辑结构可以有多种不同物理存储方式。本章将详细介绍数据结构的几大分类：线形结构、树形结构和图（网状）结构。4数据结构在计算机领域中具有重要地位，是操作系统、人工智能、计算机组成原理、程序设计、软件工程、数据库、编译原理等课程的重要基础5算法找假币方法一：n-1次612345678910?方法二：n/2次712345679108方法三：log2N次8“算法”就是解决一个问题而采取的方法和步骤，是对解题方案的准确而完整的描述，是一系列解决问题的清晰指令。9五个属性（1）确定性。（2）可行性。（3）有穷性。（4）输入性。（5）输出性。10三个层次层次内容第一层一些基本的算法，如排序、查找、递归法等算法第二层涉及算法的时间复杂度和空间复杂度，如分治法、贪心算法、动态规划法等第三层涉及智能优化算法的学习，如遗传算法、蚁群算法、聚类算法等方法11算法复杂性空间复杂度时间复杂度12

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。（1）算法的输入输出数据所占用的存储空间由要解决的问题决定，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。（2）算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。（3）算法在运行过程中临时占用的存储空间随算法的不同而异。13

算法的时间复杂度是一个函数，通常用大O符号表述，用于定量描述了该算法的运行时间。

算法中模块n的基本操作的重复执行次数计为函数f(n)，算法的时间复杂度为T(n)=O(f(n))。

常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，k次方阶O(n^k),指数阶O(2^n)。14算法评价标准1.正确性2.可读性3.健壮性4.高效率与低存储量需求15算法效率减少程序复杂性(圈复杂度V(G))16选用等效的高效率算法例如：鸡兔问题方法1：利用二重循环来实现。方法2：利用一重循环来实现。方法3：17x+y=302x+4y=90X=(4a-b)/2Y=(b-2a)/2算法表示方式程序流程图N-S图伪语言18程序流程图19N-S图20伪语言21伪语言(Pseudocode)也称伪代码，介于自然语言和计算机语言之间，并不是真正存在的编程语言。伪代码综合使用多种编程语言中语法、保留字，甚至会用到自然语言，不采用图形符号，因此书写方便、格式紧凑，便于向计算机编程语言(Pascal,C,Java……)过渡。Python语言概述Python继承于ABC语言，主要受到Modula-3的影响，Modula-3是另一种相当优美且强大的语言，为小型团体所设计，并且结合了Unixshell和C的习惯。

GuidovanRossum“Lifeisshort,youneedPython!”1.Python语言发展Python的特点解释性面向对象第三方库开源，可移植简单易学/jobbole/awesome-python-cn2.Python语言特点Python的程序开发工具1.P