When f(n) = n^.1 and g(n) = log(n)^10, does 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

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

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

0.1

x <一口>比;日志<一口> 10 x

共舞,

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

(10 <一口> k> 0.1 ≥日志<一口> 10> k

10^{0.1 k}>日志<一口> 10> k

10^{0.1 k}>k

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

10^{0.1 * 100}>100

10 <一口> 10> /blockquote>

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

0.1

x <一口>比;日志<一口> 10 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 (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 (g(n))

这个问题:

让f (n) = O (n ^ 0.1),让日志^ g (n) = 10 (n)

我们得到了极限:

极限为n->∞(n^0.1)/(log^10(n))

对极限使用L'Hospital's规则10次，得到:

极限为n->∞((0.1)^10 * ln^10(b) * n^0.1)/(10!)其中b是log

的底数

由于n项只在分子上，极限趋于无穷。

根据极限规则

log^10(n) = O(n^0.1) &0.1 n ^ ! = O (log ^ 10 (n)或n ^ 0.1 =ω(log (n) 10 ^)。