14.[单选题] 确定函数f(n)=log n^2和g(n)=sqrt(n)的关系为( )A. OB. OmegaC. thetaD. omega
14.[单选题] 确定函数$f(n)=\log n^2$和$g(n)=\sqrt{n}$的关系为( ) A. $O$ B. $\Omega$ C. $\theta$ D. $\omega$
题目解答
答案
我们来分析题目中两个函数的关系:
函数定义如下:
- $ f(n) = \log n^2 $
- $ g(n) = \sqrt{n} $
第一步:化简函数表达式
先对 $ f(n) = \log n^2 $ 进行化简。
根据对数的性质:
$\log n^2 = 2 \log n$
所以:
$f(n) = 2 \log n$
注意:这里没有说明对数的底,但在算法分析中,通常默认是 以2为底的对数,不过底数不影响渐近分析,因为不同底数之间只差一个常数倍。
因此,$ f(n) = \Theta(\log n) $
而 $ g(n) = \sqrt{n} = n^{1/2} $
第二步:比较两个函数的渐近增长速度
我们来比较 $ \log n $ 和 $ \sqrt{n} $ 的增长速度。
在渐近分析中,函数增长速度的常见顺序为:
$1 < \log n < n^a \ (0 < a < 1) < n < n \log n < n^2 < 2^n < n!$
特别地,$ \log n $ 的增长速度 远慢于 任何正指数的幂函数,比如 $ n^{1/2} = \sqrt{n} $
因此:
$\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{2 \log n}{\sqrt{n}} = 0$
这个极限为 0,说明 $ f(n) $ 比 $ g(n) $ 增长得慢得多。
第三步:确定渐近关系
我们有:
$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$
根据渐近符号的定义:
- 若 $ \lim \frac{f(n)}{g(n)} = 0 $,则 $ f(n) = o(g(n)) $,也说明 $ f(n) = O(g(n)) $,但 不是 $ \Omega(g(n)) $,更不是 $ \Theta(g(n)) $
- 所以 $ f(n) $ 是 $ g(n) $ 的 低阶无穷大,即 $ f(n) $ 增长得比 $ g(n) $ 慢
题目问的是:函数 $ f(n) = \log n^2 $ 和 $ g(n) = \sqrt{n} $ 的关系
选项是:
A. $ O $(即 $ f(n) = O(g(n)) $)
B. $ \Omega $(即 $ f(n) = \Omega(g(n)) $)
C. $ \theta $(即 $ f(n) = \Theta(g(n)) $)
D. $ \omega $(即 $ f(n) = \omega(g(n)) $,表示 $ f $ 比 $ g $ 增长得快)
但我们已经知道:
- $ f(n) = 2\log n $
- $ g(n) = \sqrt{n} $
- $ f(n) $ 增长得比 $ g(n) $ 慢
- 所以:$ f(n) = O(g(n)) $
而其他选项都不成立:
- 不是 $ \Omega $:因为 $ f(n) $ 不大于等于 $ g(n) $ 的某个常数倍
- 不是 $ \Theta $:因为两者增长阶不同
- 不是 $ \omega $:$ \omega $ 表示 $ f $ 比 $ g $ 增长得快,但实际相反
正确答案是:
$\boxed{\text{A. } O}$
即:$ f(n) = O(g(n)) $
答案解释总结:
- $ f(n) = \log n^2 = 2\log n $
- $ g(n) = \sqrt{n} $
- $ \log n $ 增长得比 $ \sqrt{n} $ 慢
- 所以 $ f(n) = O(g(n)) $,选 A
✅ 最终答案:A
解析
考查要点:本题主要考查渐近符号(大O、大Ω、θ、ω)的应用,以及对数函数与幂函数增长速率的比较。
解题核心思路:
- 化简函数表达式:利用对数性质将$f(n)=\log n^2$转化为$2\log n$。
- 比较增长速率:明确$\log n$的增长速度远慢于任何正指数幂函数(如$\sqrt{n}=n^{1/2}$)。
- 判断渐近关系:通过极限分析$\lim_{n \to \infty} \frac{f(n)}{g(n)}=0$,确定$f(n)$是$g(n)$的低阶无穷大,对应大O符号。
破题关键点:
- 对数函数与幂函数的增长差异是核心判断依据。
- 极限计算可直观验证两者的渐近关系。
函数化简
- 化简$f(n)$:
根据对数性质$\log n^2 = 2\log n$,得$f(n)=2\log n$。 - 明确$g(n)$:
$g(n)=\sqrt{n}=n^{1/2}$。
比较增长速率
- 常见函数增长顺序:
$\log n$的增长速度慢于任何正指数幂函数$n^a$($a>0$)。 - 极限分析:
计算$\lim_{n \to \infty} \frac{2\log n}{\sqrt{n}} = 0$,说明$f(n)$的增长速度远慢于$g(n)$。
判断渐近关系
- 大O符号:
$\lim_{n \to \infty} \frac{f(n)}{g(n)}=0$,说明存在常数$C$,使得$f(n) \leq C \cdot g(n)$,即$f(n)=O(g(n))$。 - 排除其他选项:
- $f(n)$不是$\Omega(g(n))$(无法下界),也不是$\Theta(g(n))$(增长阶不同)。
- $\omega$表示$f(n)$增长更快,与结论矛盾。