algorithm - 二次函数的渐近紧界，再访

Question

我想问的总体问题已在接受的答案中得到回答: asymptotic tight bound for quadratic functions 但我想专注于我无法理解的答案的子部分。

具体来说，就是这部分:“所以我们可以用 4b^2 从 sqrt(...) 的内部上方绑定(bind)”。

我无法弄清楚假设 |b|/a >= sqrt(|c|/a) 如何帮助我们达到 b^2-3ac 项的 4b^2 界限。这是我得到的:

n >= 2*(sqrt(b^2-3ac)-b)/3a

有两种情况(原答主说的)。我想了解第一个:

1. |b|/a >= sqrt(|c|/a)

(两边正方形) b^2/a^2 >= |c|/a

(乘以 a^2) b^2 >= a^2*|c|/a

(简化 a^2 和 a) b^2 >= a*|c|

(a 为正，所以 a|c| >= ac) b^2 >= ac

所以如果我们查看原始 sqrt 的内部，即 b^2-3ac，我们有

b^2-3ac >= -2ac

不是原始响应中指示的 4b^2。

有人可以帮助我了解哪里出了问题吗？

谢谢!

Answer 1

答案中有两个假设:“我们有一个正前导系数多项式”，即 a>0 和 |b|/a >= sqrt(|c|/a).

这是推导(每一步都意味着下一步):

|b|/a >= sqrt(|c|/a)
b^2/a^2 >= |c|/a, (squaring both sides)
b^2 >= |c|*a, (multiplying by a^2, since a^2>=0)
3b^2 >= 3*a*|c| = |3*a*c|, since a>0
b^2 + 3b^2 >= b^2 + |3*a*c| == b^2 + |-3*a*c| >= b^2 - 3*a*c, since |x| + |y| >= |x+y|

您显示的推导没有错误。它根本不会给你一个让你继续前进的界限。