《数据结构与算法》第一章数据结构与算法实验概要1.ppt

* * * * * * * * * * * * * * 算法的特性 (1)通用性 –对参数化输入进行问题求解 –保证计算结果的正确性 (2)有效性 –算法是有限条指令组成的指令序列 –即由一系列具体步骤组成 (3)确定性 –算法描述中的下一步应执行的步骤必须明确 (4)有穷性 –算法的执行必须在有限步内结束 –换句话说，算法不能含有死循环 * * * * * 如果时间代价是n的3次方,需要运行时间是31709791983年 * * * * * * 4．效率对算法的影响 O(logn)O(n)O(nlogn)O(n2)O(n3)O(2n)O(n!)O(nn) 例：假设CPU每秒处理10 6 个指令，对于输入规模为108的问题，时间代价T(n) = 2n2的算法要运行多长时间？ 操作次数为T(n) = T(108) = 2×(108)2 = 2×1016 运行时间为2×1016/106 = 2×1010秒 每天有86,400秒，因此需要231,481 天(634年） 操作次数为T(n) = T(108) = 2×(108)2 = 2×1016 运行时间为2×1016/109 = 2×107秒 需要231天 CPU每秒处理10 9 个指令 例：假设CPU每秒处理106个指令，对于输入规模为108的问题，时间代价为nlog n 的算法要运行多长时间？ 操作次数为 T(n) = T(108) = 108 ×log 108 = 2.66×109 运行时间为2.66×109/106 = 2.66×103秒= 44.33分钟 例：设CPU每秒处理106个指令，则每小时能够解决的最大问题规模 T(n) / 106 ≤3600 2n≤3600 ×106 ×1000 n≤41.71 2n≤3600 ×106 × 106 n≤51.67 对T(n) = 2n2， 即2n2 ≤3600 × 106 n ≤ 42 , 426 对T(n) = nlog n 即nlogn ≤3600 × 106 n ≤ 133 , 000 , 000 对T(n)=2n 即2n≤3600 ×106 n≤31.75 常用的算法设计方法 穷举法(顺序查找，百钱买百鸡) 贪心法(Huffman树，Dijkstra 算法，Prim 算法 递归法, 分治法(折半检索, 快速排序, 归并排序) 回溯法 动态规划法(最短路 Floyd 算法 ) 分枝界限法 并行算法 分布式算法 1．5数据结构在计算机科学中的地位 Web信息处理 队列、图、字符、散列、排序、检索 人工智能 表、集合、有向图、有哪些信誉好的足球投注网站树 图形图像 队列、栈、图、树、索引 数据库原理 线性表、排序、B+树 操作系统 队列、表、排序、树 编译原理 字符串、栈、散列表、语法树 数据结构 数据结构实验 算法设计与分析 高级语言程序设计 程序设计实践 离散数学 课程目标 学会如何有效地组织信息，以便支持高效的数据处理 掌握常用的基本数据结构及其应用 学会合理地组织数据，有效地表示数据，有效地处理数据 基本掌握算法分析技术 提高算法设计能力 提高使用计算机解决问题的能力 从问题求解出发 在基础理论、抽象和设计的三个层次组织知识体系 从逻辑、存储、运算的角度学习数据结构与算法， 培养学生独立地实现常用基本数据结构的抽象数据类型，注重实践能力和工程能力的培养 为将来从事计算机学科的学习、开发和研究，或其他学科应用计算机进行问题求解打下坚实的基础 学习内容 三种典型的数据结构及典型操作 两类典型算法 算法设计与分析基本知识 * * * 数据模型就是数学模型 * * * * * * * * * * * * * 从数学上看，树型结构和图结构的基本区别就是每个结点是否仅仅从属一个直接上级。而线性结构和树型结构的基本区别是每个结点是否仅仅有一个直接后继 * * 结构: 实体 + 关系 研究数据结构为为了解决问题 数据结构: (1)按照逻辑关系组织起来的一批数据, (2)按一定的存储方法把它存储在计算机中 (3)在这些数据上定义了一个运算的集合 * * * * * a1 a2 a3 a4 a5 逻辑结构 物理结构（一） 物理结构（二） a1 a2 a3 a4 a5 a3 a4 a2 a5 a1 0 struct student //数据类型 { int num; char name[12]; char sex; int age; int score[5]