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