CS5040 中级数据结构与算法

Chapter 4 Mathematical Background

| 关于   «  7. 数学证明技巧   ::   目录   ::   9. 章节小结题  »

8. 估计引论

你能从计算机科学训练中获得的最有用的生活技能之一,就是快速进行估计的能力。 这种能力有时被称为"餐巾纸背面"或"信封背面"计算。 这两个绰号都表明,得到的只是一个粗略的估计。 估计 技术是工程课程的标准内容,但在计算机科学中常常被忽视。 估计不能替代对问题的严格、详细分析,但它有助于判断何时需要进行严格分析:如果初步估计表明解法不可行,那么进一步分析很可能就不必要了。

估计可以通过以下三步过程加以形式化:

  1. 确定影响该问题的主要参数。

  2. 推导出把这些参数与问题联系起来的方程。

  3. 为参数选取取值,并应用该方程得出估计解。

做估计时,一个能让你确信估计合理的好办法是用两种不同的方法各做一遍。 一般来说,如果你想知道一个系统会输出什么,你既可以直接估计输出,也可以估计系统的输入(假定进去的东西迟早会出来)。 如果两种方法(独立地)给出相近的答案,就应当能增强你对这个估计的信心。

计算时,务必保证单位一致。 例如,不要把英尺和磅相加。 要核实结果所用的单位正确。 始终牢记:计算的输出质量取决于其输入的质量。 第 3 步中对输入参数取值的把握越不确定,输出值就越不确定。 不过,信封背面计算往往只求答案落在同一个数量级内,或者大致在两倍以内。 做估计之前,应当先确定可接受的误差范围,例如在 25% 以内、在两倍以内等等。 一旦你确信某个估计落在误差范围之内,就别再动它! 不要试图得到比你的目的所需更精确的估计。

   «  7. 数学证明技巧   ::   目录   ::   9. 章节小结题  »

关闭窗口