🔍搜索...K
QmksWeb

Appearance

《算法设计与分析》第一学期期末试卷A答案 (精选04) ​

一、计算复杂性分析（每题 10 分，共 30 分） ​

1. 若 (f(n)=\log_2^2 n)，(g(n)=\log_2 n)，判断 (f(n)) 与 (g(n)) 的渐近关系并说明理由。 ​

查看答案与解析

答案：(f(n)=\Omega(g(n)))（且 (f(n)\notin O(g(n)))，因此不可能为 (\Theta(g(n)))）。

解析（步骤完整）

  1. 写出比值极限：
$$\lim_{n\to\infty}\frac{f(n)}{g(n)} =\lim_{n\to\infty}\frac{\log_2^2 n}{\log_2 n} =\lim_{n\to\infty}\log_2 n$$

  1. 判断极限：当 (n\to\infty) 时，(\log_2 n\to +\infty)，故上式极限为 (+\infty)。

  2. 由极限推出渐近关系：比值趋于无穷大，说明 (f(n)) 增长速度严格快于 (g(n))，因此

$$f(n)=\Omega(g(n)).$$

方法总结：比较 (f(n)) 与 (g(n)) 的增长速度，常用“比值极限”或“对数/指数替换”法；若 (\lim f/g=\infty)，则 (f=\Omega(g))。

难度：⭐
考点：#渐近复杂度 #O记号 #Omega记号 #Theta记号 #极限比较

💡 学习锦囊

📖 相关公式与知识点

  • 定义：若存在 (c>0,n_0)，使 (n\ge n_0) 时 (f(n)\ge c,g(n))，则 (f(n)=\Omega(g(n)))。
  • 常用判别：若 (\lim_{n\to\infty} f(n)/g(n)=\infty)，则 (f(n)=\Omega(g(n)))。

易错点

  • 把 (\log^2 n) 误当成 (2\log n)（注意这里是平方）。
  • 看到对数就直接下结论为 (O(\log n))，忽略平方导致增长更快。
🔄 举一反三
  1. 比较 (f(n)=\log_2 n) 与 (g(n)=\sqrt{\log_2 n}) 的渐近关系。
    查看练习答案与解析

    答案：(\log_2 n=\Omega(\sqrt{\log_2 n}))。

    解析：

    $$\lim_{n\to\infty}\frac{\log_2 n}{\sqrt{\log_2 n}} =\lim_{n\to\infty}\sqrt{\log_2 n} =+\infty$$

    故 (f=\Omega(g))。

  2. 比较 (f(n)=\log_2^3 n) 与 (g(n)=n^\epsilon)（其中 (\epsilon>0) 为常数）。
    查看练习答案与解析

    答案：(\log_2^3 n=o(n^\epsilon))，即 (g(n)=\Omega(f(n)))。

    解析（关键结论）：任意固定次幂对数都比任意正幂的多项式增长慢，可用极限 (\lim_{n\to\infty}\log^k n / n^\epsilon = 0)（(k) 为常数）证明。

2. 给出汉诺塔递归算法，分析其时间复杂度。 ​

txt
void Hanoi(int n,char x, char y, char z)
{
  if(n==1) printf("将盘片%d从%c搬到%c\n",n,x,z);
  else {
    Hanoi(n-1,x,z,y);
    printf("将盘片%d从%c搬到%c\n",n,x,z);
    Hanoi(n-1,y,x,z);
  }
}
查看答案与解析

答案：时间复杂度为 (O(2^n))（更精确：执行打印次数为 (2^n-1)）。

解析（步骤完整）

  1. 建立递推式：设执行时间为 (T(n))。
    • 当 (n=1) 时，只执行一次打印，(T(1)=\Theta(1))。
    • 当 (n>1) 时，算法包含两次规模为 (n-1) 的递归调用和 (O(1)) 次常数操作（一次打印）：
$$T(n)=2T(n-1)+\Theta(1).$$
  1. 展开递推：
$$\begin{aligned} T(n) &= 2T(n-1)+1\\ &= 2\bigl(2T(n-2)+1\bigr)+1 = 2^2T(n-2)+2+1\\ &= 2^3T(n-3)+2^2+2+1\\ &\;\;\vdots\\ &= 2^{n-1}T(1)+(2^{n-2}+2^{n-3}+\cdots+2+1) \\ &= 2^{n-1}\Theta(1) + (2^{n-1}-1) \\ &= \Theta(2^n). \end{aligned}$$

因此时间复杂度为 (O(2^n))。

方法总结：遇到“两个子问题规模都为 (n-1) + 常数工作量”，常见形式 (T(n)=2T(n-1)+O(1))，直接展开或用主定理/递推求和即可。

难度：⭐
考点：#递归 #递推式 #时间复杂度 #汉诺塔

💡 学习锦囊

📖 相关公式与知识点

  • 经典递推：(T(n)=aT(n-1)+b\Rightarrow T(n)=\Theta(a^n))（当 (a>1) 且 (b=\Theta(1))）。
  • 汉诺塔移动次数：(M(1)=1)，(M(n)=2M(n-1)+1\Rightarrow M(n)=2^n-1)。

思路分析

先看“递归调用次数与规模”决定指数底数，再看“非递归部分”是常数还是线性等。

🔄 举一反三
  1. 若递推为 (T(n)=3T(n-1)+2)，求 (T(n)) 的渐近复杂度。
    查看练习答案与解析

    答案：(\Theta(3^n))。

    解析：展开可得 (T(n)=3^{n-1}T(1)+2(3^{n-2}+ \cdots +1)=\Theta(3^n))。

  2. 若递推为 (T(n)=2T(n-1)+n)，求 (T(n)) 的渐近复杂度。
    查看练习答案与解析

    答案：(\Theta(2^n))。

    解析（要点）：展开后出现 (\sum_{k=1}^{n-1}2^{n-1-k}\cdot k)，该和为 (\Theta(2^n))。

3. 顺序查找算法如下，回答平均复杂度问题。 ​

在长度为 (n) 的数组 a[0..n-1] 中顺序查找值为 (x) 的元素，找到返回 1，否则返回 0：

txt
int Find(double a[], int n, double x)
{
  int i = 0;
  while (i < n)
  {
    if (a[i] == x) break;
    i++;
  }
  if (i < n) return 1;
  else return 0;
}

回答：

  • （1）在“成功查找且每个位置等概率”的条件下，最好/最坏/平均时间复杂度分别是什么？
  • （2）若 (x) 在数组中出现的概率为 (q)，求算法的平均时间复杂度（期望比较次数）。
查看答案与解析

答案

  • （1）最好：(O(1))，最坏：(O(n))，平均（成功且等概率）：(O(n))，且成功时的期望比较次数为 (\frac{n+1}{2})。
  • （2）若 (x) 在数组中概率为 (q)，则期望比较次数：
$$E(n)=q\cdot\frac{n+1}{2}+(1-q)\cdot n,$$

因此平均时间复杂度为 (O(n))。

解析（步骤完整）

把“数组元素与 (x) 的一次比较”作为基本操作，记比较次数为 (C)。

（1）成功查找且等概率

  1. 最好情况：(a[0]=x)，只需比较 1 次，(C_{\min}=1\Rightarrow O(1))。
  2. 最坏情况（成功）：(a[n-1]=x)，比较 (n) 次，(C_{\max}=n\Rightarrow O(n))。
  3. 平均情况（成功且等概率）：若 (x) 出现在位置 (i)（(0\le i\le n-1)），则比较次数为 (i+1)，且
$$P(i)=\frac{1}{n}.$$

因此

$$E[C\mid \text{成功}] =\sum_{i=0}^{n-1}\frac{1}{n}(i+1) =\frac{1}{n}\cdot\frac{n(n+1)}{2} =\frac{n+1}{2} =\Theta(n).$$

（2）出现概率为 (q) 的一般平均

将“成功查找”和“不成功查找”合并计算期望：

  • 成功查找概率为 (q)，且（默认成功位置等概率）成功时的期望比较次数为 (\frac{n+1}{2})；
  • 不成功查找概率为 (1-q)，循环会把 (i) 从 0 比较到 (n-1)，比较次数为 (n)。

所以总期望为

$$E(n)=q\cdot\frac{n+1}{2}+(1-q)\cdot n.$$

当 (q=\frac12) 时，

$$E(n)=\frac12\cdot\frac{n+1}{2}+\frac12\cdot n=\frac{3n+1}{4}\approx\frac{3}{4}n.$$

方法总结：平均复杂度本质是“期望基本操作次数”；先写清每种情形的代价，再按概率加权求和。

难度：⭐⭐
考点：#顺序查找 #平均时间复杂度 #期望 #概率模型

💡 学习锦囊

📖 相关公式与知识点

  • 等差数列求和：(\sum_{k=1}^{n}k=\frac{n(n+1)}{2})。
  • 平均比较次数的写法：(E=\sum p_i\cdot c_i)。

易错点

  • 把“不成功查找”当成 (n+1) 次比较（本代码中是比较数组元素次数，因此是 (n) 次；若包含 i<n 的判断则另计）。
  • 平均“成功查找”与“总体（含不成功）平均”混为一谈。
🔄 举一反三
  1. 若成功位置不等概率：(P(i)=\frac{2(i+1)}{n(n+1)})（越靠后概率越大），求成功时的期望比较次数。
    查看练习答案与解析

    答案：(E=\frac{2}{n(n+1)}\sum_{i=0}^{n-1}(i+1)^2=\frac{2}{n(n+1)}\cdot\frac{n(n+1)(2n+1)}{6}=\frac{2n+1}{3}=\Theta(n))。

    解析：将 (k=i+1)，用平方和公式 (\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6})。

  2. 设数组已排序，用二分查找，比较次数的最好/最坏/平均复杂度分别是什么（以 (n) 为规模）？
    查看练习答案与解析

    答案：最好 (O(1))，最坏 (O(\log n))，平均 (O(\log n))。 解析（要点）：每次比较后把区间规模减半，比较次数约为 (\lfloor \log_2 n \rfloor + 1)。

二、简答题（每小题 5 分，共 20 分） ​

1. 算法设计的基本步骤？ ​

查看答案与解析

答案要点

  1. 问题分析：明确目标（输出）、约束条件（输入）、边界情况与评价指标。
  2. 选择数据结构与设计策略：根据问题特性选择合适的数据表示与策略（迭代/分治/动态规划/回溯/贪心等）。
  3. 描述算法：给出清晰的步骤描述（伪码/流程图/结构化语言），并定义关键变量与过程。
  4. 正确性证明：论证算法对所有合法输入都能得到正确输出（不变式、归纳、最优子结构等）。
  5. 复杂度分析与优化：分析时间/空间复杂度，必要时改进与权衡。

难度：⭐
考点：#算法设计流程 #正确性证明 #复杂度分析

💡 学习锦囊

📖 相关公式与知识点

  • 常用正确性证明：循环不变式、数学归纳法、反证法。
  • 复杂度评价：渐近上界 (O(\cdot))、下界 (\Omega(\cdot))、紧界 (\Theta(\cdot))。
🔄 举一反三
  1. 简述“算法分析”通常包括哪些指标？
    查看练习答案与解析

    答案：主要包括时间复杂度、空间复杂度；在工程中也会考虑常数因子、缓存/IO、可并行性与稳定性等。 解析：理论课以渐近复杂度为主；实际实现需结合平台与数据分布。

2. 能用递归解决的问题应满足哪些基本条件？ ​

查看答案与解析

答案要点

  1. 可分解为规模更小的同类子问题：原问题可转化为一个或多个结构相同、规模更小的子问题。
  2. 递归必须有终止条件（基本情形）：存在可直接求解的最小规模输入，且能被触达。
  3. 规模严格缩小且调用次数有限：每次递归都使规模朝终止条件推进，否则会无限递归。

难度：⭐
考点：#递归 #递归终止条件 #递归分解

💡 学习锦囊

📖 相关公式与知识点

  • 递归通常对应递推式，用于复杂度分析：(T(n)=aT(n/b)+f(n)) 或 (T(n)=aT(n-1)+f(n))。
🔄 举一反三
  1. 为什么“有终止条件”还不够？还需要“规模严格缩小”？
    查看练习答案与解析

    答案：如果每次递归不缩小规模，即使写了终止条件也可能永远到不了终止状态（例如不断对同一规模调用自己），仍会无限递归。 解析：终止条件是“存在”，规模缩小是“可达”。

3. 简述动态规划与分治法的异同。 ​

查看答案与解析

答案要点

  • 相同点：都把原问题分解为子问题，再由子问题解组合得到原问题解；都依赖“最优子结构/可组合性”。
  • 不同点：
    • 分治法：子问题通常相互独立、不重叠；递归求解再合并结果（如归并排序）。
    • 动态规划：子问题通常重叠；用“记忆化/表格法”复用子问题结果，避免重复计算；常配合“阶段/状态转移”建模。

难度：⭐⭐
考点：#动态规划 #分治 #重叠子问题 #最优子结构

💡 学习锦囊

📖 相关公式与知识点

  • DP 三要素：状态定义、状态转移方程、边界与遍历顺序。
  • “重叠子问题”是 DP 相比分治的关键差异点。
🔄 举一反三
  1. 举一个“分治适用但 DP 不占优势”的例子，并说明原因。
    查看练习答案与解析

    答案：归并排序。
    解析：子问题互不重叠，分治每个子问题只算一次；DP 的缓存并不会减少工作量。

  2. 举一个“DP 明显优于纯分治”的例子，并说明原因。
    查看练习答案与解析

    答案：斐波那契数列。
    解析：(F(n)=F(n-1)+F(n-2)) 子问题大量重叠；DP/记忆化能把指数级降为线性。

4. 简述贪心法适用问题应具有的性质。 ​

查看答案与解析

答案要点

  1. 贪心选择性质：存在一种局部最优选择策略，使得每一步做出的局部最优选择最终能导向全局最优解。
  2. 最优子结构性质：问题的最优解包含子问题的最优解；做出一次选择后，剩余部分仍是同类规模更小的最优化问题。

难度：⭐⭐
考点：#贪心 #贪心选择性质 #最优子结构

💡 学习锦囊

📖 相关公式与知识点

  • 贪心正确性证明常见套路：交换论证（exchange argument）、归纳证明、反证。
🔄 举一反三
  1. 说明“最优子结构”与“贪心选择性质”哪个更强？为什么？
    查看练习答案与解析

    答案：贪心选择性质更强。
    解析：很多 DP 问题有最优子结构但不具备贪心选择性质，无法用每步局部最优直接得到全局最优（如 0/1 背包）。

三、算法设计题（每小题 15 分，共 30 分） ​

1. (k) 个有序序列的 2 路合并：给出最优与最差合并顺序，并写出伪码。 ​

已知合并长度为 (m,n) 的两序列需要比较 (m+n-1) 次。设 (k) 个序列长度为 (l_1,l_2,\dots,l_k)。

查看答案与解析

答案（结论）

  • 最优（比较次数最少）：每次都合并当前最短的两个序列长度（哈夫曼式合并/最优合并模式）。
  • 最差（比较次数最多）：每次都合并当前最长的两个序列长度。

解析（为什么这样最优）

每次合并会产生一个新长度 (l=l_i+l_j)，并把该长度继续参与后续合并。一次合并的代价为 (l_i+l_j-1)，而新长度会在后续再次被多次“累加进代价”。因此，为了让“被重复参与的长度”尽可能小，应优先合并短序列（与哈夫曼编码的最优加权路径长度同构）。

伪码（最优合并：最小堆）

txt
OptimalMergeCost(lengths[1..k]):
  build a min-heap H with all lengths
  cost = 0
  while H.size > 1:
    x = extractMin(H)
    y = extractMin(H)
    cost += (x + y - 1)
    insert(H, x + y)
  return cost

伪码（最差合并：最大堆）

txt
WorstMergeCost(lengths[1..k]):
  build a max-heap H with all lengths
  cost = 0
  while H.size > 1:
    x = extractMax(H)
    y = extractMax(H)
    cost += (x + y - 1)
    insert(H, x + y)
  return cost

复杂度分析

  • 建堆 (O(k))，每次取出/插入 (O(\log k))，循环 (k-1) 次：
    • 总时间 (O(k\log k))
    • 额外空间 (O(k))

难度：⭐⭐⭐
考点：#最优合并模式 #贪心 #优先队列 #哈夫曼思想

💡 学习锦囊

📖 相关公式与知识点

  • “最优合并模式”可视为哈夫曼树：每次取最小两个权值合并。
  • 代价结构：合并产生的新长度会在后续被重复计算，因此早期合并顺序影响很大。

易错点

  • 只写“每次合并最短两段”而不给出可执行的堆实现/伪码。
  • 把比较次数写成 (m+n) 而漏掉 (-1)。
🔄 举一反三
  1. 设长度为 ([2,3,4,7])，求最优合并的总比较次数。
    查看练习答案与解析

    答案：27。

    解析：

    • 合并 2 和 3 得 5，代价 4；
    • 合并 4 和 5 得 9，代价 8（(4+5-1=8)）；
    • 合并 7 和 9 得 16，代价 15；
    • 总计 (4+8+15=27)。
      因此正确总比较次数为 27。
  2. 若合并代价改为 (m+n)（没有 (-1)），最优策略是否改变？
    查看练习答案与解析

    答案：不改变，仍是每次合并最短两段。
    解析：(-1) 是常数偏移，不改变“让大长度尽量晚出现”的核心贪心结构。

2. 采用分治法求整数序列中的最大与最小元素，写出思路与伪码。 ​

查看答案与解析

答案（思路）

将区间 ([l,r]) 二分为 ([l,mid]) 与 ([mid+1,r])，分别递归求左右区间的 ((\min,\max))，再合并得到整段的 ((\min,\max))。

伪码

txt
MaxMin(a, l, r):
  if l == r:
    return (a[l], a[l])         // (min, max)
  if r == l + 1:
    if a[l] < a[r]:
      return (a[l], a[r])
    else:
      return (a[r], a[l])
  mid = (l + r) // 2
  (min1, max1) = MaxMin(a, l, mid)
  (min2, max2) = MaxMin(a, mid+1, r)
  return (min(min1, min2), max(max1, max2))

复杂度分析

递推为 (T(n)=2T(n/2)+O(1)\Rightarrow T(n)=O(n))。比较次数方面，该算法能做到接近最优（约 (3n/2-2) 次比较）。

难度：⭐⭐
考点：#分治 #最大最小 #递归合并 #比较次数优化

💡 学习锦囊

📖 相关公式与知识点

  • 分治递推：(T(n)=2T(n/2)+O(1)\Rightarrow O(n))。
  • 比较次数最优下界：同时找最大最小至少需要 ( \lceil 3n/2 \rceil - 2 ) 次比较（可用成对比较法达到）。

思路分析

把“最大/最小”看成可合并的局部信息：左右区间各自的 max/min 合并只需 2 次比较。

🔄 举一反三
  1. 用“成对比较法”在一次扫描中求最大最小，比较次数是多少？
    查看练习答案与解析

    答案：约 (3n/2-2) 次（(n) 为偶数时精确为 (3n/2-2)）。
    解析：每对元素先比较 1 次分出大/小，再分别与当前 max/min 比较各 1 次，共 3 次/对。

四、算法分析题（每小题 10 分，共 20 分） ​

1. 给定赋权无向图 (G=(V,E))，求最小权顶点覆盖，给出具体结果与算法设计思路。 ​

（题图见同目录 images/）

查看答案与解析

答案（具体结果）

由题图可读出各顶点权值：

  • (w(1)=1,;w(3)=1,;w(4)=1,;w(5)=1,;w(7)=10,;w(2)=100,;w(6)=100)

边集包含右侧三角形 ((2,4),(2,5),(4,5)) 以及与 7 相连的 ((7,1),(7,3),(7,6),(7,4))。

  1. 处理三角形 ({2,4,5})：要覆盖边 ((4,5)) 必须选 4 或 5；若不选 2，则 ((2,4)) 与 ((2,5)) 只能靠同时选 4、5 覆盖。由于 (w(2)=100) 很大，最优选择为 ({4,5})，权重为 (1+1=2)。
  2. 处理顶点 7 相关边：边 ((7,4)) 已被 4 覆盖；剩余 ((7,1),(7,3),(7,6))。
    • 选 7：一次覆盖三条边，代价 (w(7)=10)
    • 不选 7：必须选 ({1,3,6})，代价 (1+1+100=102) 因此应选 7。

综上，最小权顶点覆盖为：

$$U^\*=\{4,5,7\},\qquad W(U^\*)=w(4)+w(5)+w(7)=1+1+10=12.$$

答案（算法思路概述）

可用**分支限界法（Branch and Bound）**求解最小权顶点覆盖（NP-困难问题的精确解法之一）：

  1. 状态/解向量：对每个顶点 (v_i) 取 (x_i\in{0,1})，表示是否选入覆盖集合 (U)。
  2. 可行性判定：当对所有边 ((u,v)\in E) 都满足 (x_u=1) 或 (x_v=1) 时，该解为顶点覆盖。
  3. 目标函数：最小化 (\sum_{v_i\in V} w(v_i),x_i)。
  4. 搜索树：按某种顺序依次决定顶点取 0/1（左分支选入、右分支不选入）。
  5. 下界（限界函数）：对“尚未覆盖的边”，构造一个快速可计算的权重下界（例如基于未覆盖边的端点最小权估计），用以剪枝：若当前已选权重 + 下界 ≥ 当前最优解，则剪去该分支。
  6. 结点选择策略（优先队列）：用优先队列按“当前已选权重 + 下界”从小到大扩展结点（Best-First）。

为什么需要下界：仅按“权重小优先”并不能保证有效剪枝；要想在指数搜索中尽快收敛，需要一个尽可能紧的下界。

方法总结：NP-困难的精确求解通常＝搜索 + 剪枝；剪枝依赖下界估计的质量。

难度：⭐⭐⭐
考点：#最小权顶点覆盖 #分支限界 #下界剪枝 #优先队列

💡 学习锦囊

📖 相关公式与知识点

  • 顶点覆盖：对每条边至少选一个端点。
  • 分支限界三件套：状态表示 + 下界函数 + 结点扩展策略。

易错点

  • 把“顶点覆盖”与“独立集/匹配”概念混淆。
  • 只写“用优先队列”但不给出可行性检查与剪枝依据。
🔄 举一反三
  1. 写出“可行性检查”的伪码（给定 (x_i) 判断是否为顶点覆盖）。
    查看练习答案与解析

    答案（伪码）：

    txt
    IsVertexCover(x):
  for each edge (u,v) in E:
    if x[u] == 0 and x[v] == 0:
      return false
  return true

    解析：只要存在一条边两端都未选入，就不满足覆盖。

  2. 若图是二分图，最小（不带权）顶点覆盖可用什么定理多项式求解？
    查看练习答案与解析

    答案：Kőnig 定理（最大匹配大小 = 最小顶点覆盖大小），可先求最大匹配再导出最小顶点覆盖。 解析：该结论只适用于二分图且是“不带权/或特殊权重”情形，带权版本需用其他方法。

2. 用动态规划求最长递增子序列（LIS）长度，给出状态与转移，并写伪码。 ​

示例：a = {2,1,5,3,6,4,8,9,7}，LIS 长度为 5（如 {1,3,4,8,9}）。

查看答案与解析

答案（状态与转移）

定义一维 DP：

  • 状态：(dp[i]) 表示“以 (a[i]) 作为结尾”的最长递增子序列长度（只考虑下标 (0..i)）。
  • 初始化：(dp[i]=1)（单个元素本身长度为 1）。
  • 转移：对每个 (i)，枚举所有 (0\le j<i)，若 (a[j]<a[i])，则
$$dp[i]=\max\bigl(dp[i],\;dp[j]+1\bigr).$$

最终答案：(\max_{0\le i\le n-1} dp[i])。

伪码

txt
LISLength(a[0..n-1]):
  for i = 0..n-1:
    dp[i] = 1
    for j = 0..i-1:
      if a[j] < a[i]:
        dp[i] = max(dp[i], dp[j] + 1)
  ans = dp[0]
  for i = 1..n-1:
    ans = max(ans, dp[i])
  return ans

复杂度

  • 时间：双重循环 (O(n^2))
  • 空间：(O(n))

难度：⭐⭐
考点：#动态规划 #最长递增子序列 #状态转移 #O(n^2)

💡 学习锦囊

📖 相关公式与知识点

  • LIS 的常见两种解法：(O(n^2)) DP（易写易懂）；(O(n\log n)) 贪心 + 二分（维护 tails 数组）。

易错点

  • 条件应为严格递增：使用 (a[j] < a[i])，不要误写成 (\le)。
  • (dp[i]) 的定义一定要是“以 (i) 结尾”，否则转移会写乱。
🔄 举一反三
  1. 若要求“最长非递减子序列”（允许相等），转移条件如何改？
    查看练习答案与解析

    答案：把条件 (a[j] < a[i]) 改为 (a[j] \le a[i])。 解析：非递减允许相等元素连接，DP 框架不变，只改比较符号。

  2. 给出 (O(n\log n)) 方法的核心思路（不要求完整证明）。
    查看练习答案与解析

    答案：维护数组 tails[len] 表示“长度为 len 的递增子序列可能的最小结尾值”；遍历每个元素，用二分找其应更新的位置，从而保持 tails 单调并实现 (O(\log n)) 更新。 解析：tails 的长度就是 LIS 长度；该方法求长度很快，但恢复具体序列需额外记录前驱。

你正在阅读的是会员专属文档，💕 限时特惠进行中
你尚未登录，目前新用户可获3天体验会员，去登录