algorithm - 停下来想想《算法设计手册》第 2 版中的 : Hip to the Squares?

Question

目前我正在阅读 Steven Skiena 撰写的算法设计手册，第 2 版，我偶然发现了一个问题。

在第 2 章中，他解释了算法分析，其中包括 Big Oh 表示法，我不明白他对停下来思考:Hip to the Squares?的解决方案

问题:是 (x + y)² = O(x² + y²)。

他的解决方案是 (x + y)² <= 3(x² + y²)，这意味着 c >= 3(Big Oh 定义中的常数)。

这是我的解决方案:

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

我在这里错过了什么？

Answer 1

我不知道他从哪里得到 3，但这是如何证明 (x + y)² <= 2(x² + y< sup>2):

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

至于为什么你的解决方案是错误的，你是从你想证明的开始，这很棘手。我喜欢在不等式旁边打一个问号，以提醒它还未知:

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

然后每个后续步骤都应该是前一步的隐含步骤，这样如果你得出一个绝对正确的陈述，你可以反转这些步骤并获得证明。下一步就好了:

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

现在您的第 3 步既不是您想要证明的东西，也不是您知道的东西。你可以说的是，一切在 x 和 y 上都是对称的，所以我们可以假设 x = max(x, y)(因为如果 y 是更大的那个，你可以做任何你想做的事，但使用 x 和 y交换)。

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