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

清华大学电子工程系课件——常用算法设计
常用算法设计(1)
孙甲松
清华大学电子工程系
sun@thsp.ee.tsinghua.edu.cn

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