停下来思考：Hip to the Squares？来自《算法设计手册》第二版。

Question

我正在阅读Steven Skiena的The Algorithm Design Manual, 2nd Edition，遇到了一个问题。

在第二章中，他解释了算法分析，其中包括大O符号，但我不理解他对Stop and Think: Hip to the Squares?的解决方案。

问题：(x + y)² = O(x² + y²)是否成立？

他的解决方案是(x + y)² <= 3(x² + y²)，这意味着c >= 3（从大O符号的定义中得出的常数）。

这是我的解决方案：

1. (x + y)² <= c(x² + y²)
2. x² + 2xy + y² <= c(x² + y²)
3. x = max(x, y)
4. x² + 2x² + x² <= c(x² + x²)
5. 4x² <= 2cx²
6. 2x² <= cx²
7. c >= 2

我错在哪里了？

- user2555240

Answer 1

我不知道他怎么得出了3，但是下面是如何证明 (x + y)² <= 2(x² + y²)的方法：

2(x² + y²) - (x + y)² = 2x² + 2y² - x² -2xy - y² = x² - 2xy + y² = (x - y)² >= 0

至于为什么你的解法是错的，因为你从想要证明的东西开始，这很棘手。我喜欢在不等式旁边加一个问号，提醒自己还不确定：

1. (x + y)² <=? c(x² + y²)

然后每一步都应该暗示前一步，如果到达一个绝对正确的陈述，就可以反转步骤并证明。接下来一步没问题：

2. x² + 2xy + y² <=? c(x² + y²)

现在你的第三步既不是你想证明的，也不是你知道是正确的。你可以说一切都对称于x和y，所以我们可以假设x = max(x, y)（因为如果y更大，你可以将要做的操作用x和y交换即可）。

但正如Douglas Zare指出的那样，第4步并不等同于第2步，因为你增加了不等式的两边。

- JWWalker

Answer 2

首先，确切的常数通常并不重要。使用这种渐进分析的一个目的是它比Knuth、Flajolet和Sedgewick等人使用的精确分析更简单。因此，即使您发现3不是最佳可能常数，那又怎样呢？

其次，您犯了一个错误，如果您不仅编写一堆方程式希望它们是自明的，而是编写逻辑连接，就会更容易发现。这就像注释您的代码。

您想选择c以使不等式成立。这意味着您的蕴涵应该是向上的：7蕴涵6蕴涵5蕴涵4蕴涵2蕴涵1。但是，您替换了2的左侧为较大的表达式，并将2的右侧替换为较大的表达式以获得不等式4，这个部分对于向下的蕴涵是有效的，但对于向上的蕴涵是无效的。通过更多的工作，您仍然可以确定更好的常数，但是您尚未证明这一点，因此您的推导是不完整的。

我猜想书中的解决方案是，如果c>=1，则c(x^2+y^2)>=cx^2+y^2。如果c>=3且x>=y，则cx^2>=x^2+2xy，因此cx^2+y^2>=x^2+2xy+y^2。

- Douglas Zare

---

在得出 cx^2 >= x^2+2xy 这个不等式时，我认为你假设了 x >= 0。但是我没有看到问题中给出这个条件。 - JWWalker

@JWWalker：不，x>=0并非必需。我使用的是| x | >= | y |。在计算机科学中，人们通常不会在渐近分析中关心负变量。 - Douglas Zare