3.10. 常见误解¶
3.10.1. 常见误解¶
渐近分析 是计算机科学专业本科生所面对的最具智力挑战的主题之一。大多数人觉得 增长率 和渐近分析令人困惑，因而会对概念或术语产生误解。了解常见的困惑之处有助于避免它们。
区分 上界 和 下界 这两个概念的一个问题是，对你将遇到的大多数算法而言，很容易辨认出该算法的真实增长率。在完全了解某个成本函数的情况下，该成本函数的上界和下界总是相同的。因此，只有在你对被度量对象的了解不完整时，区分上界和下界才有意义。如果这种区分仍不清楚，那么你应当 阅读分析问题的相关内容 。我们用 \(\Theta\) 记法来表示：我们所知道的上界和下界的增长率之间没有实质性差别（对简单算法而言通常如此）。
一个常见的错误是把上界或下界的概念与 最坏情况 或 最好情况 的概念混为一谈。最好、最坏或 平均情况 各自为某个特定的输入实例（平均情况下则是特定的一组实例） 定义了一个成本 。相比之下，上界和下界描述的是我们对那种成本度量的 增长率 的认识。所以，要定义算法或问题的增长率，我们需要确定所度量的是什么（最好、最坏还是平均情况），并确定如何描述我们所知道的该成本度量的增长率（大 O、 \(\Omega\) 还是 \(\Theta\) ）。
对给定规模 \(n\) 的输入，算法的上界并不等于该算法的最坏情况。这里被界定的不是实际成本（对给定的 \(n\) 值，实际成本是可以确定的），而是成本的 增长率 。单个点，比如 \(n\) 的某个特定值，不可能有增长率。增长的 速率 适用于输入规模发生 变化 时成本的 变化 。同样，下界也不等于给定规模 \(n\) 的最好情况。
另一个常见的误解是，认为算法的最好情况发生在输入规模尽可能小时，或者认为最坏情况发生在输入规模尽可能大时。正确的是，每个可能的输入规模都存在最好和最坏情况实例。也就是说，对于给定规模（比如 \(i\) ）的所有输入，其中有一个（或多个）规模为 \(i\) 的输入是最好情况，有一个（或多个）规模为 \(i\) 的输入是最坏情况。通常（但并非总是！），我们可以刻画任意规模下的最好输入情况，也可以刻画任意规模下的最坏输入情况。理想情况下，随着输入规模增大，我们可以确定所刻画的最好、最坏和平均情况的增长率。
