performance - 当 f(n) = n^.1 且 g(n) = log(n)^10 时，f(n) = Ω(g) 吗？

Question

有人告诉我“任何指数都胜过任何对数”。

但是当指数在0和1之间时，对数的执行时间不是增长得更快吗？所以按照这个逻辑，f = O(g)

我很难选择是遵循我的直觉还是遵循别人告诉我的，但我得到的告诉可能并不完全准确。

Answer 1

让我们在这里尝试一些数学。一个重要的事实是对数函数是单调递增的，这意味着如果

log f(x) ≤ log g(x)

然后

f(x) ≤ g(x)

现在，让我们看看它在这里做了什么。我们有两个函数，x^0.1 和 log¹⁰ x。如果我们获取他们的日志，我们会得到

log (x^0.1) = 0.1 log x

和

log (log¹⁰ x) = 10 log log x

由于 log log x 的增长速度比 log x 慢得多，直观上我们可以看到函数 x^0.1 最终将超过 log¹⁰ x。

现在，让我们将其形式化。我们想要找到 x 的某个值，使得

x^0.1 > log¹⁰ x

为了让数学更容易，我们假设这些是以 10 为底的对数。如果我们假设对于某些 k，x​​ = 10^k，我们会得到

(10^k)^0.1 ≥ log¹⁰ 10^k

10^{0.1 k} > log¹⁰ 10^k

10^{0.1 k} > k

现在，取 k = 100。现在我们得到了

10^{0.1 * 100} > 100

10¹⁰ > 100

这显然是正确的。由于两个函数都是单调递增的，这意味着对于 x ≥ 10¹⁰⁰，确实

x^0.1 > log¹⁰ x

这意味着 x^0.1 = O(log¹⁰ k) 不成立。

希望这有帮助!