algorithm - Big Oh Notation 查找 n0 和 c

Question

我在看这个问题：

证明 100+5 ∈ (²) （即 100+5 是 ² 的上界）

() ≤ () for all ≥ 0
所以它变成 100+5 ≤ ²

答案是：

0 ≈ 25.05（² 算法截取算法的数）和 = 4，所以当增加到 25.05 以上时，无论如何它仍然会证明 100+5∈² 为真

我的问题是：你如何得出 0 = 25.05 和 = 4？它是一种猜测和试验方法，还是有适当的方法来获得那个特定的答案？或者你只需​​要从 1 开始，然后一路向上看它是否有效？

标签： algorithmstructurecomputer-sciencediscrete-mathematics

Answer 1

解决此类问题的一个好方法是首先修复 c 让我们在这个例子中取 4

然后你所要做的就是用一个简单的等式计算出 n0

100n + 5 = 4n^2 <=> 4n^2 - 100n - 5 = 0 <=> n = 25.05 或 n = -0.05 在这里你可以注意到它们在 -0.08 和 25.05 中相交两次，并且你想要 n0 这样之后 100n +5 总是低于 4n^2 -0.05 不是 25.05 > -0.05 并且在 25.05 它们相交所以 n0 = 25.05 。

在修复 c 并尝试计算 n0 之前，您可以尝试 n0 的大数字以了解它是否是上限。