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

Question

我正在尝试找出函数的大 O 时间复杂度

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

和函数

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

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

谢谢!

Answer 1

在使用 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)。

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

希望这对您有所帮助!