1.1编程的灵魂——数据结构算法程序.ppt

《算法艺术与信息学竞赛》刘汝佳 黄亮 著 1.1 编程的灵魂—— 数据结构+算法=程序 版权说明 本系列课件为刘汝佳、黄亮著《算法艺术与信息学竞赛》配套课件 凡是购买《算法艺术与信息学竞赛》的读者，均可免费获得此课件，供自己学习 此课件不得用于商业用途，若要用于教育用途，请自觉与作者联系，以获得支持 使用说明 ★符号表示重点要求 △符号表示只需要了解，不用深入学习 第1章 算法与数据结构 1.1 编程的灵魂——数据结构+算法=程序 1.2 基本算法 1.3 数据结构（1）——入门 1.4 数据结构（2）——拓宽与应用举例 1.5 动态规划 1.6 状态空间搜索 目录 一、绪论 二、算法实现和比较 三、算法分析 四、函数增长和记号★ 五、递归式的递归树分析 六、算法设计与分析实例★★ 七、计算模型与难解问题 八、总结 一、绪论 绪论 编程: 实现(implement)一个方法(method)去解决(solve)一个问题(problem). 这个方法通常和所使用的计算机独立, 但可以用很多计算机语言写成, 并运行在多种计算机上 这样的方法称为算法(algorithm). 一方面, 它只提供了解决问题的抽象步骤而不是程序本身, 另一方面, 它又适合被实现为计算机程序从而被执行, 即: 算法是抽象的, 但很有实用价值 算法是很多计算机科学领域研究的核心对象 算法的组成 本文讨论的算法由三部分组成 输入: 需要处理的数据 输出: 算法执行完毕后得到的结果 算法步骤: 把输入转化为输出的步骤 算法步骤的表示 自然语言: 不精确但直观的描述算法步骤 伪代码: 通用的精确表示, 但不能直接运行 代码: 精确表示, 可以直接运行, 但没有通用性 算法与数据结构 本文研究的算法应当是能转化成计算机程序从而被执行. 它可以调用已有的算法, 但是不能使用没有办法完成的步骤 本文研究的算法是面向计算机的, 它处理数据, 即把输入转化成输出. 大部分算法需要专门设计组织和使用数据的方法. 在计算机科学中, 数据的组织和使用依靠数据结构(data structure). 算法与数据结构紧密联系 算法的选择 解决同一个问题, 通常有多种算法. 小规模问题(small problems), 各种算法都可以 大规模问题(large problems), 尽量选择时间、空间耗费小的算法. 有时候时间耗费少的空间耗费多, 则需要根据实际情况权衡(trade-off) 为什么要学算法设计? 硬件投资? 速度增加10~100倍 算法改进? 一百万倍的提速相当普遍 大项目: 分解为独立任务, 有一些关键任务的算法影响到整个系统的性能 二、算法实现与比较 算法的实现 代码的可重用性: 一般来说本文尽量调用已经实现好的算法 需要重新实现基本算法的情况 更好的理解算法, 为特定应用微调算法 新计算环境, 无库可用, 且硬件特性不一致 实现的优化程度: 本文一般只考虑不过分牺牲算法效率下相对自然简洁的实现方式 真实的实现: 过度优化、错误处理、维护性 实验比较 侧重点 算法分析: 两个算法同阶, 只相差一个常数 实验比较: 一个运行3秒, 一个运行30秒 算法分析和实验比较 实验比较可以验证算法分析的结果. 是否真的只相差一个常数? 算法分析可以帮助估算实际运行时间. 愿意等待10个小时? 实验比较的步骤 步骤一: 实现算法. 简单的算法并不困难, 但是复杂的算法的实现具有挑战性, 若想得到高效的实现需要关注一些算法细节而不光是编码细节 步骤二: 设计测试数据. 一般来说可以使用实际数据、随机数据和特殊(甚至错误)数据. 随机数据保证分析结果是针对算法而不是数据的, 而特殊数据确保算法能正确处理一切给它的输入 其他 常见错误 不注意程序效率. 高效算法往往更复杂, 但是一但写成, 能节约大量的执行时间 过分注意程序效率. 常数时间的优化, 当此常数和基数都不太大时并不是很必要 实验比较的附加收获 提出的“算法改进”真会提高效率吗? 确定待定的参数 三、算法分析 算法分析的主要任务 任务 任务一: 比较同一问题的不同算法 任务二: 预测算法在新环境下的性能 任务三: 设置算法参数 在很多情况下比”实验比较”成本低 算法分析的挑战 算法分析的结果 情况一: 透彻的理解, 精确的公式 情况二: 无法得到精确的公式 可能是输入情况太复杂 可能是实现细节太复杂, 难以精确分析 算法分析的基础: 理想模型 抽象操作 抽象操作(abstract operations). 对于单一操作(如加法)的算法, 运行时间 = 操作时间 * 操作次数 (不考虑cache等体系结构方面的影响) 操作时间取决于计算机 操作次数取决于算法 算法分析: 只考虑算法特性, 因此只考虑操作次数 算法分析的对象 抽