CSP-S 2023 第一轮 第3题：假设n是图的顶点的个数，m是图的边的个数，为求解某一问题有下面四种不同时间复杂

题目

假设 $n$ 是图的顶点的个数，$m$ 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于 $m=\Theta(n)$ 的稀疏图而言，下面的四个选项，哪一项的渐近时间复杂度最小（）。

选项

• A. $O(m\sqrt{\log n\cdot \log\log n})$
• B. $O(n^2+m)$
• C. $O(\dfrac {n^2} {\log m}+ m\log n)$
• D. $O(m+n\log n)$

答案

A

题解

答案是 A。

对于稀疏图，$m=\Theta(n)$，也就是 $m$ 与 $n$ 同阶，因此 $\log m=\Theta(\log n)$。代入各选项：

关键是比较 A 和 D。 两者的增长率之比为 \[ \frac{n\sqrt{\log n\cdot\log\log n}}{n\log n} =\sqrt{\frac{\log\log n}{\log n}} \longrightarrow 0, \] 因此 A 比 D 增长得慢。

而 D 又比 C、B 增长得慢，因为 \[ \frac{n\log n}{n^2/\log n} =\frac{(\log n)^2}{n}\longrightarrow 0. \]

所以，从增长慢到增长快排列为： \[ \boxed{A<D<C<B} \]