我正在尝试找出函数的大 O 时间复杂度
f(x) = (x4 + x2 + 1)/(x4 + 1)
和函数
f(x) = (x3 + 5 log x)/(x4 + 1)
如果我可以消除分数分母上的 +1 项，这将非常简单，因为那时我可以除以 x4。我怎样才能消除它们？
谢谢!
最佳答案
在使用 big-O 时，它通常有助于确定值的下限和上限，而不必获得准确的值。
例如，给定 (x4 + x2 + 1)/(x4 + 1)，一件事可能是有帮助的是注意对于 x ≥ 1，
(x4 + x2 + 1)/(2x4) ≤ (x4 + x2 + 1)/(x4 + 1) ≤ (x4 + x2 + 1)/x4
现在你已经把所有东西都夹在中间了，你可以从那里简化所有东西，非常简单地得到
(1/2)(x4 + x2 + 1)/(x4) ≤ (x4 + x2 + 1)/(x4 + 1) ≤ (x4 + x2 + 1)/x4
(1/2)(1 + 1 / x2 + 1 / x4) ≤ (x4 + x2 + 1)/(x4 + 1) ≤ 1 + 1 / x2 + 1 / x4
不等式的前半部分表明表达式为 Ω(1)，后半部分表明其为 O(1)。因此，表达式为Θ(1)。
尝试使用相同的技巧来简化其中的第二个。
希望这对您有所帮助!
关于math - 通过简化分母获得时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19825596/