清华大学电子工程系课件——常用算法设计

清华大学电子工程系课件——常用算法设计常用算法设计(1)孙甲松清华大学电子工程系sun@thsp.ee.tsinghua.edu.cn2007.9.1.概述算法是为解决某个问题的而设计的计算或者操作的步骤和方法。有了算法，才可以编写程序即使某人对某种计算机语言（C/C++语言）非常熟悉，如果自己不会根据要解决的问题设计算法，也不可能编写出程序解决相应的问题对于只是简单叙述的问题，能自己想出合适的算法来解决。比如，请编写程序给出从n个数中取k个的全部解对于给出的问题，不但要能设计出算法，而且要能设计出简单易行的优秀算法1.概述(续1)解决同一个问题不同的人（甚至同一个人）可能会写出几种不同的算法。但算法有优劣之分，往往差距很大。往往有这样的情况：同样一个问题，根据一种算法编写的程序可能需要几天甚至几个星期才能得到最终的解；而根据另一个好的算法编写的程序可能只需要几小时甚至几分钟就能得到同样的解。追求的最优算法当然应该是计算次数最少、所需存储空间最小的。但这两者往往不可兼得。在解决实际问题时，经常需要“以时间换空间”或“以空间换时间”的情况，这跟所用的计算机的内存和速度有关，需要折中考虑。1.概述(续2)虽然设计算法，尤其是设计出好的算法是一件非常困难的工作，但是设计算法也不是没有方法可循。人们经过几十年来的工作，总结和积累了许多行之有效的方法，了解和掌握这些方法会给我们解决问题提供一些思路。经常采用的算法设计