嘿伙计们，我正在从 Dasgupta 的算法书中解决一些大问题，并且被困在一些问题上。
1) f(n) = n^0.1 g(n) = (log n)^10
根据对数和幂的渐近复杂性的最佳答案，“对于任何正常数 a，b，log(n)^a 始终为 O(n^b)。” 所以对于 1)，f = omega(g)
2) f(n) = n^1.01 g(n) = n log^2 n 我的猜测是 f = omega(g)。这个例子是正确的还是不同的情况，因为 log 是平方并乘以 n？
请提供有关您为解决此类问题所采取的步骤的任何说明
您对第一个问题的回答是正确的，您对该规则的应用也是如此。这是任何 a > 0 的 log(n) = O(n^a) 的证明（这显然等同于上述规则）：
The derivative of n^a is a*(n^(a-1))
The derivative of log(n) = 1/n
Therefore, for large enough n, the derivative of n^a is more than the derivative of log(n)
Therefore, for large enough n, n^a > log(n)
Therefore log(n) = O(n^a)
你对第二个问题的回答是正确的。这是一个证明：
g(n) = O(f(n)) if and only if log(log(n)) = O(n^0.01)
log(log(n)) = O(log(n)) so log(log(n)) = O(O(n^0.01)) = O(n^0.01)