目前我正在阅读 Steven Skiena 撰写的算法设计手册,第 2 版,我偶然发现了一个问题。
在第 2 章中,他解释了算法分析,其中包括 Big Oh 表示法,我不明白他对停下来思考:Hip to the Squares?的解决方案
问题:是 (x + y)2 = O(x2 + y2)。
他的解决方案是 (x + y)2 <= 3(x2 + y2),这意味着 c >= 3(Big Oh 定义中的常数)。
这是我的解决方案:
- (x + y)2 <= c(x2 + y2)
- x2 + 2xy + y2 <= c(x2 + y2)<
- x = max(x, y)
- x2 + 2x2 + x2 <= c(x2 + x 2)
- 4x2 <= 2cx2
- 2x2 <= cx2
- c >= 2
我在这里错过了什么?
最佳答案
我不知道他从哪里得到 3,但这是如何证明 (x + y)2 <= 2(x2 + y< sup>2):
2(x2 + y2) - (x + y)2 = 2x2 + 2y2 - x2 -2xy - y2 = x2 - 2xy + y2 = (x - y)2>= 0
至于为什么你的解决方案是错误的,你是从你想证明的开始,这很棘手。我喜欢在不等式旁边打一个问号,以提醒它还未知:
- (x + y)2 <=? c(x2 + y2)
然后每个后续步骤都应该是前一步的隐含步骤,这样如果你得出一个绝对正确的陈述,你可以反转这些步骤并获得证明。下一步就好了:
- x2 + 2xy + y2 <=? c(x2 + y2)
现在您的第 3 步既不是您想要证明的东西,也不是您知道的东西。你可以说的是,一切在 x 和 y 上都是对称的,所以我们可以假设 x = max(x, y)(因为如果 y 是更大的那个,你可以做任何你想做的事,但使用 x 和 y交换)。
但正如 Douglas Zare 指出的那样,第 4 步不等同于第 2 步,因为您增加了不等式的两边。
关于algorithm - 停下来想想《算法设计手册》第 2 版中的 : Hip to the Squares?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32106822/