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

Question

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

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

我很难选择是遵循我的直觉还是听我说的，但我听的可能并不完全准确。

Answer 1

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

日志 f(x) ≤ 日志 g(x)

然后

f(x) ≤ g(x)

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

日志 (x ^0.1 ) = 0.1 日志 x

和

日志（日志¹⁰ x）= 10 日志日志 x

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

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

x ^0.1 > 对数¹⁰ x

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

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

10 ^{0.1 k} > 对数¹⁰ 10 ^k

10 ^{0.1 k} > k

现在，取 k = 100。现在我们有了

10 ^{0.1 * 100} > 100

10 ¹⁰ > 100

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

x ^0.1 > 对数¹⁰ x

这意味着x ^0.1 = O(log ¹⁰ k)是不正确的。

希望这可以帮助！

Answer 2

渐近分析真正关注的是长期关系（因为 n 假设较大的值，函数的值如何比较）？它也忽略了常数，这就是为什么你有时会看到像 f(x) = 10000000*x = O(x^2) 这样的奇怪情况。

对于较大的 值n，f(n) > g(n)这才是真正重要的。

Answer 3

n^0.1 = big omega(log^10(n))另一种通过使用限制规则来验证的方法？

限制规则是：

限制为 n-> 无穷大 f(n)/g(g)。

如果极限为正无穷大，则 f(n) != O(g(n)) & g(n) = O(f(n)) 或 f(n) = big omega(g(n))

如果限制为 0，则 f(n) = O(g(n)) & g(n) != O(f(n))

如果极限是正实数，则 f(n) = O(g(n)) & g(n) = O(f(n)) 或 f(n) = big theta(g(n))

对于这个问题：

让 f(n) = O(n^0.1) 并让 g(n) = log^10(n)

这给了我们限制：

限制为 n->infinity (n^0.1)/(log^10(n))

对限制使用 L'Hospital's规则 10 次，我们得到：

限制为 n->infinity ((0.1)^10 * ln^10(b) * n^0.1)/(10!) 其中 b 是对数的基数

由于 n 项仅在分子中，因此极限接近无穷大。

由极限规则

log^10(n) = O(n^0.1) & n^0.1 != O(log^10(n) 或 n^0.1 = 大欧米茄(log^10(n))。