当 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.1k> log¹⁰ 10^k

10^0.1k> k

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

10^{0.1 * 100}> 100

10¹⁰> 100

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

x^0.1> log¹⁰ 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) = 大欧米伽(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) = 大 t​​heta(g(n))

对于此问题：

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

这给了我们极限：

限制为 n->无穷大 ​​(n^0.1)/(log^10(n))

使用 L'Hospital 的极限规则 10 次，我们得到：

限制为 n->无穷大 ​​((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))。