(log(n))^log(n) 和 n/log(n)，哪个更快？

Question

f(n)=(log(n))^log(n)

g(n)= n/log(n)

f = O(g(n))?

- Soup

---

简短回答：是的。更详细的回答是，在代码上运行分析器。big-o 不适用于实际性能测量，只适用于“如果 N 趋近无穷大会发生什么”类型的问题。而“O(x)”与问题有什么关系呢？如果 f=O(g(n))，那么 n 是一个常数吗？如果不是，为什么不是 f(n)=O(g(n))？还是 f 与 f(n)=(log(n))^log(n) 相关？ - Lasse V. Karlsen

如果这是作业，请使用标签“homework”进行翻译。 - BlueRaja - Danny Pflughoeft

请参见https://dev59.com/q3E95IYBdhLWcg3wb9hb#2307314。 - BalusC

大O符号并不是关于速度，而是关于限制行为的。 - Gumbo

@Gumbo，我不知道O()等价于lim()，并且总是将其与性能测量相关联。这种符号在英语中常见吗？ - devio

Answer 1

对两边同时取对数：

log(f(n)) = log(log n) * log n

log(g(n)) = log(n) - log(log(n)) = log(n)(1 - log(log(n))/log(n))

显然log(log(n))占优势，所以g是O(f)。f不是O(g)。由于这是作业，你可能需要填写细节部分。

只需尝试大一些的数字，就可以很容易地获得答案的想法。1024是2的10次方，因此取n=1024：

f(n) = 10^10

g(n) = 1024/10。

显然这并不是一个证明，但我认为我们可以看出谁赢了这场比赛。

- Steve Jessop

Answer 2

f(n)增长比g(n)快，当且仅当f(eⁿ)也增长比g(eⁿ)快，因为指数函数严格增加到正无穷（请自行证明）。现在f(eⁿ) = nⁿ和g(eⁿ) = eⁿ/n，你可以引用已知的结果。

- kennytm

---

这不是完全正确的。1-1/x是严格递增的，但并不意味着如果f比g增长得更快，那么1-1/f增长得比1-1/g更快。它们可能以相同的大O速率增长（毫不奇怪，因为1-1/x收敛于一个常数）。因此，你的结果是正确的，但原因并非如所述。 - Steve Jessop

@Steve：（1）“当且仅当”（2）你应该比较f（1-1/x），而不是1-1/f（x）。 - kennytm

好的，那么对于 f(n) = n^2，g(n) = n. 1 - 1/n^2，(1 - 1/n)^2 和 1 - 1/n，它们都是 O(1)，所以它们并不增长得更快（严格地说），尽管其中一些严格大于其他一些（对于 n > 1）。exp 对于我们的目的比严格增加要“好”，并证明了一个更强的结果。 - Steve Jessop

+1。那么，您甚至不需要exp严格增加，只需要它及其反函数都趋于无穷大。我想。 - Steve Jessop

Answer 3

如果 Limit[f[x] / g[x], x -> Infinity] = Infinity，那么 f[x] 的增长速度比 g[x] 快。

当 x -> Infinity 时，Limit[Log[x] ^ Log[x] / (x / Log[x])] = + Infinity。

因此，Log[x] ^ Log[x] 的增长速度比 x / Log[x] 快。

- yassin

---

如果您有Mathematica，可以使用Plot[Log[x]^(Log[x])/(x/Log[x]), {x, 0, 100}]来查看它。 - yassin

http://www.wolframalpha.com/input/?i=plot+%28log%28x%29%29%5elog%28x%29+and+x%2Flog%28x%29+from+1+to+100 - kennytm

Answer 4

Mathematica 给出当 n 趋近于无穷大时的 f(n) / g(n) 的极限为无穷大，这意味着 f 增长得更快。这表明 g(n) 属于 (=) O(f(n))。

如果你没有 Mathematica，可以使用 this 作为示例。

- IVlad

Answer 5

f 远远大于 n^loglog(n) -1 . log n

- Fakrudeen