算法设计与分析（一）算法基础课件

《算法设计与分析（一）算法基础课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析2011.9(ACM创新实验班2010级)写在讲课前一、什么是算法算法就是计算的方法。数·学数：1，2，3，4，…学：偶数、质数、微积分…之数的学问算·法算：加、减、乘、除法：何时、何处用何计算之算的方法写在讲课前（续）举个例子：排序问题描述：将一组数按从小到大的顺序整理有序基本思想：小的数往前排，大的数往后排怎么排？算法冒泡排序选择排序归并排序快速排序堆排序Shell排序…每种算法都是一组特定的规则，规定了一种处理数据的运算方法写在讲课前（续）问题：既然每种方法都可以实现排序之目的，何必费心研究这么多排序算法？目的一：是

2、不是人们的遐想？起码不是瞎想目的二：算法和算法间是有区别的性质不同：稳定、不稳定性能不同：速度、空间适用场合不同没有万全的算法适合所有的应用的。怎么选择：根据性能、结合需求、综合选择如何了解每种算法的性能？算法的分析人们乐衷于寻找不同的方法以在不同的应用要求下求解各种问题写在讲课前（续）二、算法分析了解算法的性能：算法速度：快还是慢？如何衡量？怎么比较？空间使用量(计算机算法*)：大还是小？如何衡量？怎么比较？其它方面的性质等。写在讲课前（续）实例分析：排序算法的理论分析：（略）编程序测试1.冒泡排序真的很慢吗？数据集元素个数：10、20

3、、1000、10000…2.快速和归并排序都是O(nlogn)的时间复杂度，到底谁快呢？原因是什么？3.冒泡排序会不会比快速排序快？来自于实测的结论：可能。写在讲课前（续）三、为什么要学习算法1.编程序的需要任何程序都需要算法。thecoreofcomputerscience程序=数据结构+算法2.改造世界的需要世界上还有很多很多的问题等待你解决，有无数的程序等待你去编。3.国家综合实力的体现（大）从软实力的角度，算法是国家科技生产力的核心。是国家综合实力的体现。写在讲课前（续）四、算法太多了，学不过来是的，千万的问题、万千的算法。都学过

4、来是不可能的。甚至专一门已经很了不起。课堂学习只能关注于算法设计与分析的基本策略与方法，为设计更复杂、更有效的算法奠定基础。更多的知识需要同学们以后不断学习，甚至创造出新的算法。写在讲课前（续）五、算法的学习过程：痛苦并快乐着1.枯燥的过程繁vs烦：学习一个算法如同做一道数学题，多了呢？ACMICPC的训练过程，谁学谁知道2.智慧的积累方法的掌握、技术的升华3.理论的贡献算法成就或在于理论的贡献，而不仅仅是技术的提高。如何成就好算法：好思想+好技术写在讲课前（续）六、好算法从理论的角度说，好算法应该有较低的时间复杂度（高速）和空间复杂度（

5、低耗），但好的算法还要依靠好的实现，需要理论与技术、技巧的结合才能最终实现好的算法。从应用的角度说，能有效地解决问题的算法都是好算法——不管黑猫白猫，抓住老鼠就是好猫；不管A算法、B算法，能解决问题就是好算法（实用了点）。概述课程核心：介绍算法设计与分析的基本理论、方法和技术，奠定算法设计的基础。教学目的：在理论学习上，掌握算法分析与设计的基本理论和方法，培养设计新算法和分析算法复杂性的能力。在实践教学上，掌握算法实现的技术、技巧，学习算法的正确性验证、效率分析、优化技术，以及算法在实际问题中的分析与应用。培养独立研究和创新能力。概述（续

6、）课程内容：基本概念：算法的定义、性质、分析算法的基本方法等分治策略（Divideandconquer）贪心方法（Greedymethod）动态规划（DynamicProgramming）图算法（GraphAlgorithms）回溯与分枝限界……专题综合实践概述（续）本课程需要的基础数据结构程序设计语言（C/C++）：结构化设计数学基础操作系统、编译概述（续）授课形式:课堂教学：（√）课堂讨论：专题、解题报告上机实践：需要提交实验报告概述（续）主要参考书计算机算法基础，余祥宣等编著，华中科技大学出版社Introductiontoalgor

7、ithms,ThomasH.Cormen,etc.,secondedition,TheMITPress.AlgorithmDesign，MichaelT.Goodrich算法设计与分析，王晓东，清华大学出版社概述（续）其它参考书TheArtofComputerProgramming,DonaldE.Knuth.Volume1-3,SecondEdition.DataStructures,Algorithms,andApplicationsinC++(Part3)SartajSahni,ChinaMachinePressetc.一、算法基础

8、参考资料：《计算机算法基础》第二章《Introductiontoalgorithms》Chapter1、Chapter31.1算法的定义及特性1.什么是算法？算法如数字、计算一样，是一个基本概