算法设计和的分析(一)

《算法设计和的分析(一)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、其一：“瞎想”，就像玩智力游戏，人们乐衷于寻找不同的方法解决各种各样的问题。其二：研究的需要，算法和算法间是有区别的，我们有必要去研究，去分析。性质不同：稳定、不稳定性能不同：速度、空间适用场合不同其三，应用的需求，问题有千百万种，没有万能的算法适合所有的应用。需要我们找出算法的设计规律，并设计出解决问题的新算法怎么选择：根据性能、结合需求、综合选择如何了解每种算法的性能？算法的分析二、算法分析了解算法的性能：算法速度：快还是慢？如何衡量？怎么比较？空间使用量(计算机算法*)：大还是小？如何衡量？怎么比较？其它方面的性质等。实例分析

3、：排序算法的理论分析：（略）编程序测试1.冒泡排序真的很慢吗？数据集元素个数：10、20、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++）：结构化设计数学基础操作系统、编译授课形式:课堂教学：（√）课堂讨论：专题、解题报告上机实践：需要提交实验报告概述（续）考核方式:考试：（√）综合成绩=卷面成绩*80%+平时成绩*20%

7、平时成绩=作业+上机实验+考勤主要参考书计算机算法基础，余祥宣等编著，华中科技大学出版社Introductiontoalgorithms,ThomasH.Cormen,etc.,secondedition,TheMITPress.AlgorithmDesign，MichaelT.Goodrich算法设计与分析，王晓东，清华大学出版社其它参考书TheArtofComputerProgramming,DonaldE.Knuth.Volume1-3,SecondEdition.DataStructures,Algorithms,andAp

8、plicationsinC++(Part3)SartajSahni,ChinaMachinePressetc.一、算法基础参考资料：《计算机算法基础》第二章《Introductiontoalgorithms》Chapter1、Chap