math - 通过简化分母来获得时间复杂度？

Question

我试图找到函数的大 O 时间复杂度

f(x) = (x ⁴ + x ² + 1)/(x ⁴ + 1)

和功能

f(x) = (x ³ + 5 log x)/(x ⁴ + 1)

如果我可以消除分数分母上的 +1 项，这将非常简单，因为那时我可以只除以 x ⁴。我怎样才能消除它们？

谢谢！

Answer 1

big-O 表示法的定义是这样的：当存在 M - real 且 x0>0 时，我们写 f(x) = O(g(x)) 使得对于每个 x > x0 为真，|f(x) | ≤ M |g(x)|。

对于案例 1，我们将证明 f(x) = O(1)。令 g(x) = 1。选择 M = 2 和 x0 = 0 给我们

|(x ⁴ + x ² + 1) / (x ⁴ + 1)| = (x ⁴ + x ² + 1) / (x ⁴ + 1) ≤ (x^4 + (x^4 + 1) + 1) / (x ⁴ + 1) (因为 x ² <= x ⁴ + 1对于 x > 0) = 2 = M|g(x)|

因此，在所有这些之后，我们将得到 f(x) = O(1)。我希望这对第二个例子也有帮助。我想你明白了。您只需选择适当的 M、x0 和 g 并证明不等式。

Answer 2

使用 big-O 时，它通常有助于对值进行下限和上限，而不必获得确切的值。

例如，给定 (x ⁴ + x ² + 1)/(x ⁴ + 1)，可能有用的一件事是注意对于 x ≥ 1，

(x ⁴ + x ² + 1)/(2x ⁴ ) ≤ (x ⁴ + x ² + 1)/(x ⁴ + 1) ≤ (x ⁴ + x ² + 1)/x ⁴

现在你已经把所有东西都夹在中间了，你可以从那里简单地简化所有东西以获得

(1/2)(x ⁴ + x ² + 1)/(x ⁴ ) ≤ (x ⁴ + x ² + 1)/(x ⁴ + 1) ≤ (x ⁴ + x ² + 1)/x ⁴

(1/2)(1 + 1 / x ² + 1 / x ⁴ ) ≤ (x ⁴ + x ² + 1)/(x ⁴ + 1) ≤ 1 + 1 / x ² + 1 / x ⁴

不等式的前半部分告诉你你的表达式是 Ω(1)，后半部分告诉你它是 O(1)。因此，表达式为 Θ(1)。

尝试使用相同的技巧来简化其中的第二个。

希望这可以帮助！