文档介绍：算法设计与分析 (ACM创新实验班 2010级)
写在讲课前
一、什么是算法
算法就是计算的方法。
数·学
数:1,2,3,4,…
学:偶数、质数、微积分…之数的学问
算·法
算:加、减、乘、除
法:何时、何处用何计算之算的方法
写在讲课前(续)
举个例子:排序
问题描述:将一组数按从小到大的顺序整理有序
基本思想:小的数往前排,大的数往后排
怎么排?算法
冒泡排序
选择排序
归并排序
快速排序
堆排序
Shell排序
…
每种算法都是一组特定的规则,规定了一种处理数据的运算方法
写在讲课前(续)
问题:既然每种方法都可以实现排序之目的,何必费心研究这么多排序算法?
目的一:是不是人们的遐想?起码不是瞎想
目的二:算法和算法间是有区别的
性质不同:稳定、不稳定
性能不同:速度、空间
适用场合不同
没有万全的算法适合所有的应用的。
怎么选择:根据性能、结合需求、综合选择
如何了解每种算法的性能?算法的分析
人们乐衷于寻找不同的方法以在不同的应用要求下求解各种问题
写在讲课前(续)
二、算法分析
了解算法的性能:
算法速度:快还是慢?如何衡量?怎么比较?
空间使用量(计算机算法*):大还是小?如何衡量?怎么比较?
其它方面的性质等。
写在讲课前(续)
实例分析:
排序算法的理论分析:(略)
编程序测试
?
数据集元素个数:10、20、1000、10000…
(nlogn)的时间复杂度, 到底谁快呢?原因是什么?
?
来自于实测的结论:可能。
写在讲课前(续)
三、为什么要学****算法
任何程序都需要算法。 the core puter science
程序= 数据结构+ 算法
世界上还有很多很多的问题等待你解决,有无数的程序等待你去编。
(大)
从软实力的角度,算法是国家科技生产力的核心。是国家综合实力的体现。
写在讲课前(续)
四、算法太多了,学不过来
是的,千万的问题、万千的算法。都学过来是不可能的。甚至专一门已经很了不起。
课堂学****只能关注于算法设计与分析的基本策略与方法,为设计更复杂、更有效的算法奠定基础。
更多的知识需要同学们以后不断学****甚至创造出新的算法。
写在讲课前(续)
五、算法的学****过程:痛苦并快乐着
繁vs烦:学****一个算法如同做一道数学题,多了呢?
ACM ICPC的训练过程,谁学谁知道
方法的掌握、技术的升华
算法成就或在于理论的贡献,而不仅仅是技术的提高。
如何成就好算法:好思想+好技术
写在讲课前(续)
六、好算法
从理论的角度说,好算法应该有较低的时间复杂度(高速)和空间复杂度(低耗),但好的算法还要依靠好的实现,需要理论与技术、技巧的结合才能最终实现好的算法。
从应用的角度说,能有效地解决问题的算法都是好算法——不管黑猫白猫,抓住老鼠就是好猫;不管A算法、B算法,能解决问题就是好算法(实用了点)。