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