(log n)/ (log(log n)) 的顺序是什么？
What is the order of (log n)/ (log(log n))?
f=(log n)/ (log(log n))的顺序是什么？
是f= O(log n)吗？这是为什么？
h=(log n) * (log log n)的顺序是什么？
难道也是h= O(log n)？为什么是正确的？
Is f= O(log n)?
是
Is it also h= O(log n)?
没有
证明：
使用正式定义:
f(n) = O(g(n)) means there are positive constants c and n0, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0. The values of c and n0 must be fixed for the function f and must not depend on n.
f = O(logn) <=> (log n)/ (log(log n)) = O(logn)
因此，您需要找到 c 和 n0，使得所有 n ≥ n0 的 0 ≤ (log n)/ (log(log n)) ≤ c*logn。假设对数的底数是b（其实无所谓，可以考虑b in {2,e,10}）。如果您选择 c=1 和 n0=b^b^2，则所有 n ≥ b^b^2 都选择 0 ≤ (log n)/ (log(log n)) ≤ logn。
- 第一部分是正确的，因为
log n ≥ log b^b^2 = b^2 ≥ 0 和 log(log n) ≥ log(log b^b^2) = 2 ≥ 0
- 第二部分也是如此，因为变成了
log(log n) ≥ 1和log(log n) ≥ log(b^2) = 2 ≥ 1.
与第一个证明类似，需要证明不能选择c和n0使得(log n) * (log(log n)) ≤ c*logn对所有n ≥ n0。对于大 n，它变成 (log(log n)) ≤ c，因为 log n 不能是 0。很明显，您不能选择 c，因为它不适用于 n > b^b^c。
f=(log n)/ (log(log n))的顺序是什么？
是f= O(log n)吗？这是为什么？
h=(log n) * (log log n)的顺序是什么？
难道也是h= O(log n)？为什么是正确的？
Is
f= O(log n)?是
Is it also
h= O(log n)?没有
证明：
使用正式定义:
f(n) = O(g(n)) means there are positive constants c and n0, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0. The values of c and n0 must be fixed for the function f and must not depend on n.
f = O(logn) <=> (log n)/ (log(log n)) = O(logn)因此，您需要找到
c和n0，使得所有n ≥ n0的0 ≤ (log n)/ (log(log n)) ≤ c*logn。假设对数的底数是b（其实无所谓，可以考虑bin{2,e,10}）。如果您选择c=1和n0=b^b^2，则所有n ≥ b^b^2都选择0 ≤ (log n)/ (log(log n)) ≤ logn。- 第一部分是正确的，因为
log n ≥ log b^b^2 = b^2 ≥ 0和log(log n) ≥ log(log b^b^2) = 2 ≥ 0 - 第二部分也是如此，因为变成了
log(log n) ≥ 1和log(log n) ≥ log(b^2) = 2 ≥ 1.
- 第一部分是正确的，因为
与第一个证明类似，需要证明不能选择
c和n0使得(log n) * (log(log n)) ≤ c*logn对所有n ≥ n0。对于大n，它变成(log(log n)) ≤ c，因为log n不能是0。很明显，您不能选择c，因为它不适用于n > b^b^c。