log(n)=O(n^1/100) 的 n_0 是什么？
what is the n_0 for which log(n)=O(n^1/100)?
我知道log(n)=O(n^1/100)，根据
你如何正式证明这一点？你需要找到 n_0 这样对于每个 n>n_0 确实 log(n) < k*n^(1/100) 对于某个常数 k，你如何找到那些 n_0 和 k?
寻找 n_0 使得 log(n_0) < (n_0)^(1/100)
您不需要找到 n_0。您只需要找到一个有效的 n_0。你可以选择一个非常大的 n_0.
让n_0 = 10^1000。它是一个 1 后跟 1000 个零。那么：
(n_0)^(1/100) = 10^10 = 10000000000;log(n_0) = log_10(n_0) / log_10(e) = 1000 / log_10(e) < 4000.
我假设 log 表示自然对数。但是正如你所看到的，二进制对数、自然对数和十进制对数无论如何都只相差一个很小的常数因子。
所以我们找到了 n_0 使得 log(n_0) < (n_0)^(1/100)。现在我们需要证明对于所有 n > n_0, log(n) < n^(1/100).
为所有 n > n_0、log(n) < n^(1/100)
证明
为此，我们可以证明差值 f(n) = n^(1/100) - log(n) 是 n 的增函数。
这个函数在正实数上是可微的；它的导数是：
f'(n) = 100 / (n^(99/100)) - (1 / n)
f'(n) = (100 n - n^(99/100)) / (n * n ^(99/100))
f'(n) > 99 n / (n * n ^(99/100)) = 99 / (n ^ (99/100))
f'(n) > 0
因此差异在严格增加；因为 f(n_0) > 0，我们有 f(n) > f(n_0) > 0 所有 n > n_0.
我知道log(n)=O(n^1/100)，根据n_0 这样对于每个 n>n_0 确实 log(n) < k*n^(1/100) 对于某个常数 k，你如何找到那些 n_0 和 k?
寻找 n_0 使得 log(n_0) < (n_0)^(1/100)
您不需要找到 n_0。您只需要找到一个有效的 n_0。你可以选择一个非常大的 n_0.
让n_0 = 10^1000。它是一个 1 后跟 1000 个零。那么：
(n_0)^(1/100) = 10^10 = 10000000000;log(n_0) = log_10(n_0) / log_10(e) = 1000 / log_10(e) < 4000.
我假设 log 表示自然对数。但是正如你所看到的，二进制对数、自然对数和十进制对数无论如何都只相差一个很小的常数因子。
所以我们找到了 n_0 使得 log(n_0) < (n_0)^(1/100)。现在我们需要证明对于所有 n > n_0, log(n) < n^(1/100).
为所有 n > n_0、log(n) < n^(1/100)
证明
为此，我们可以证明差值 f(n) = n^(1/100) - log(n) 是 n 的增函数。
这个函数在正实数上是可微的；它的导数是：
f'(n) = 100 / (n^(99/100)) - (1 / n)
f'(n) = (100 n - n^(99/100)) / (n * n ^(99/100))
f'(n) > 99 n / (n * n ^(99/100)) = 99 / (n ^ (99/100))
f'(n) > 0
因此差异在严格增加；因为 f(n_0) > 0，我们有 f(n) > f(n_0) > 0 所有 n > n_0.