2025-2026学年下学期月考

2025-2026学年下学期月考试卷

一、（25 分）

令 $m = n^{\log \log n}$。请按渐进增长顺序从小至大排列以下的函数。

$$mn, \qquad n, \qquad n^{\log n}, \qquad m^{\log \log n}$$

---

二、（25 分）

给定 $n$ 个区间 $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$。请合并所有重叠的区间，并返回一个不重叠的区间数组（顺序可以任意）。

Example: Input $[15,18], [1,3], [8,10], [3,6]$

Output $[[8,10], [1,6], [15,18]]$

---

三、（25 分）

给出下面各个递推式中 $T(n)$ 的渐进上界和下界。假设当 $n \le 2$ 时，$T(n)$ 为常数。使你的界尽可能紧，并给出理由。

(1) $T(n) = 2T(n / 2) + n^4$

(2) $T(n) = T(7n / 10) + n$

(3) $T(n) = 16T(n / 4) + n^2$

(4) $T(n) = 7T(n / 3) + n^2$

(5) $T(n) = 7T(n / 2) + n^2$

(6) $T(n) = 2T(n / 4) + \sqrt{n}$

(7) $T(n) = T(n - 2) + n^2$

---

四、（25 分）

给定一个升序排列的数组，在某个未知位置进行了旋转。例如：$[0,1,2,4,5,6,7]$ 旋转变成了 $[4,5,6,7,0,1,2]$。设 $A = [a_1, a_2, \ldots, a_n]$ 为旋转后的数组。给定一个目标值 $s$，请在数组中查找该值的下标，如果不存在则返回 $-1$。要求时间复杂度为 $O(\log n)$。