大厂真题 / 华为

华为 7.24 笔试真题 - AI岗

本场考试概述

考试时间：2026年7月24日 考试岗位：AI岗 难度评级：中等

考点分析：

选择题（20道）：随机变量线性组合、Activation Checkpointing、概率密度、正则化、交叉熵、PCA、多模态融合、无监督学习、相关系数、PagedAttention、困惑度、滑动窗口、SVD、向量相似度、残差连接与多模态训练
第一题：MoE 动态路由——Top-K 排序 + 容量约束模拟（难度中等）
第二题：流水线连续划分——动态规划 + 滑动窗口最小堆（难度中等偏难）

建议策略：

选择题既考基础公式，也考大模型训练与推理中的工程机制，需要分清训练显存、推理显存和计算代价
第一题严格按 token 顺序处理；每个 token 内按“分数降序、编号升序”确定候选专家，专家容量彼此独立
第二题先写出连续划分 DP，再观察合法前驱是随右端点单调右移的区间，用最小堆把平方级转移降到 $O(pn\log n)$

选择题（20道）

一、单选题

1、设随机变量 $X\sim N(1,2)$、$Y\sim N(2,3)$，且 $X,Y$ 相互独立。令 $Z=2X-Y$，则 $Z$ 的方差为？

A. $7$
B. $11$
C. $5$
D. $13$

答案：B
难度：简单
考点：数学—概率论/随机变量线性组合
解析：独立随机变量的协方差为 $0$，因此

\[\operatorname{Var}(Z)=2^2\operatorname{Var}(X)+(-1)^2\operatorname{Var}(Y)=4\times2+3=11.\]

均值不影响方差；若不独立，还需要加入 $2\times2\times(-1)\operatorname{Cov}(X,Y)$。

2、在训练大模型时使用 Activation Checkpointing（激活检查点）的主要目的是？

A. 减少模型参数量
B. 提高推理吞吐量
C. 通过反向传播时重算部分前向结果来降低激活显存
D. 消除梯度通信

答案：C
难度：简单
考点：大模型—训练显存优化
解析：Activation Checkpointing 只保存部分层的激活，反向传播需要时重新执行相应前向计算，用额外计算换取更低的激活显存。它不会减少参数量，也不是面向推理阶段的优化。

3、随机变量 $X$ 的概率密度为 $f(x)=c(1-x^2)$（$-1\le x\le1$），其他位置为 $0$。常数 $c$ 为？

A. $\dfrac12$
B. $\dfrac23$
C. $\dfrac34$
D. $1$

答案：C
难度：简单
考点：数学—概率密度
解析：概率密度在全定义域上的积分必须为 $1$：

\[1=c\int_{-1}^{1}(1-x^2)\,dx =c\left[x-\frac{x^3}{3}\right]_{-1}^{1} =c\cdot\frac43,\]

故 $c=\dfrac34$。

4、L2 正则化提高模型稳定性的主要原因是？

A. 限制权重过大，使模型对输入扰动不那么敏感
B. 自动删除所有无关特征
C. 保证训练损失降为 $0$
D. 将所有权重变成完全相同的值

答案：A
难度：简单
考点：机器学习—正则化
解析：L2 正则化在目标函数中加入权重平方和惩罚，倾向于得到较小、较平滑的参数，降低模型方差以及对噪声的敏感程度。它通常不会产生大量严格为 $0$ 的权重，也不保证训练误差为 $0$。

5、三分类任务的真实标签为 one-hot 向量 $[0,1,0]$，模型预测概率为 $[0.1,0.8,0.1]$，单样本交叉熵损失为？

A. $-\log 0.1$
B. $-\log 0.8$
C. $-\log 0.2$
D. $0.8$

答案：B
难度：简单
考点：机器学习—交叉熵
解析：多分类交叉熵为 $-\sum_i y_i\log p_i$。one-hot 标签只有真实类别对应项为 $1$，所以损失就是该类别预测概率的负对数，即 $-\log0.8$。

6、在对不同量纲的特征做 PCA 前，通常先进行标准化，其主要原因是？

A. 使 PCA 变成非线性方法
B. 保证所有主成分的方差相同
C. 避免大尺度特征仅因量纲较大而主导主成分
D. 将特征数量直接减少一半

答案：C
难度：简单
考点：机器学习—PCA/数据预处理
解析：PCA 寻找方差最大的方向。若不同特征量纲相差很大，数值尺度大的特征会主导协方差矩阵。标准化让各特征在可比尺度上参与主成分提取，但不会使 PCA 非线性。

7、多模态模型中的 Late Fusion（后期融合）通常是指？

A. 在输入层直接拼接所有模态的原始数据
B. 各模态由独立编码器处理，在决策层融合预测结果或高层表示
C. 只保留信息量最大的一个模态
D. 每一层都执行跨模态注意力

答案：B
难度：简单
考点：多模态—融合策略
解析：Late Fusion 先让不同模态相对独立地编码或完成预测，再在较后的决策层进行融合。输入级拼接属于 Early Fusion；每层跨模态交互则属于更深层的中间融合。

8、神经网络隐藏层的主要作用之一是？

A. 只能复制输入特征
B. 保证模型目标函数是凸函数
C. 通过非线性变换学习更高阶的特征表示
D. 使模型不再需要训练数据

答案：C
难度：入门
考点：深度学习—表示学习
解析：隐藏层把线性变换与激活函数组合起来，逐层构造更抽象、更高阶的非线性特征。若所有层都没有非线性激活，多层线性映射仍等价于单个线性映射。

9、面对没有任何标签的数据，希望算法自动发现类别结构，应优先采用哪类方法？

A. 监督学习
B. 强化学习
C. 无监督学习
D. 在线蒸馏

答案：C
难度：入门
考点：机器学习—学习范式
解析：无标签数据上的自动分组是典型的聚类问题，属于无监督学习。监督学习需要标签，强化学习需要环境反馈的奖励信号。

10、两个评分者采用的评分尺度不同，但希望衡量两组评分的线性一致程度，较合适的指标是？

A. 均方误差
B. 曼哈顿距离
C. Pearson 相关系数
D. 准确率

答案：C
难度：简单
考点：数学—统计相关性
解析：Pearson 相关系数衡量两个变量的线性相关程度，对正比例缩放和平移不敏感，适合比较不同评分尺度下的变化趋势。均方误差和曼哈顿距离会直接受到尺度差异影响。

11、若 PagedAttention 的 block size 设置为 $1$，最可能带来的问题是？

A. KV Cache 完全无法共享
B. 必然产生严重的块内碎片
C. 每个序列只能保存一个 token
D. 页表元数据开销增大，并可能因访问过于离散而降低访存效率

答案：D
难度：中等
考点：大模型—PagedAttention/KV Cache
解析：block size 为 $1$ 几乎消除了块内未使用空间，但每个 token 都需要独立的块映射，页表等元数据数量最大，物理块访问也更零散。工程上需要在内部碎片和管理、访存开销之间折中。

12、在语言模型能够合理建模数据的前提下，高质量、自然且连贯的文本通常表现为？

A. 困惑度更高
B. 困惑度恒为 $1$
C. 困惑度更低
D. 困惑度与文本质量完全无关

答案：C
难度：简单
考点：大模型—困惑度
解析：困惑度是平均负对数似然的指数形式。模型对自然、连贯文本赋予的条件概率通常更高，因此其负对数似然和困惑度更低。跨模型、跨词表直接比较困惑度时则需要谨慎。

13、某 decoder-only 模型使用长度为 $20$ 的滑动窗口注意力。Prefill 输入 $30$ 个 token，随后 Decode 生成 $15$ 个 token。若实现始终只保留窗口内 KV，则最终 KV Cache 长度和单个新 token 可见的上下文长度分别为？

A. $20,20$
B. $30,20$
C. $45,45$
D. $15,20$

答案：A
难度：中等
考点：大模型—滑动窗口注意力/KV Cache
解析：序列总长度已经超过窗口大小，但旧 KV 会被窗口机制淘汰，所以最终缓存最多保留 $20$ 个 token；每个新 token 的注意力也只覆盖最近 $20$ 个位置。Prefill 和 Decode 的长度不会突破固定窗口上限。

14、对实矩阵作奇异值分解 $A=U\Sigma V^T$，下列说法正确的是？

A. $U$、$V$ 可以取为正交矩阵
B. $\Sigma$ 的奇异值可以为负数
C. 只有方阵才能进行 SVD
D. $U$、$V$ 必须相同

答案：A
难度：简单
考点：数学—线性代数/SVD
解析：完整 SVD 中，$U$ 和 $V$ 分别由左右奇异向量组成，可取为正交矩阵；$\Sigma$ 对角线上的奇异值非负。任意矩形矩阵都可以做 SVD，且一般没有 $U=V$。

15、关于余弦相似度和欧氏距离，下列说法正确的是？

A. 余弦相似度主要比较方向，欧氏距离同时受到方向和向量长度影响
B. 二者都只考虑向量长度
C. 二者都完全忽略向量长度
D. 余弦相似度只能用于一维向量

答案：A
难度：简单
考点：机器学习—向量度量
解析：余弦相似度对正比例缩放不敏感，关注夹角；欧氏距离是两向量差的模，方向和长度变化都会影响结果。若向量先做 L2 归一化，二者才存在单调对应关系。

二、多选题

16、关于 Activation Checkpointing，下列说法正确的是哪些？

A. 反向传播时通常需要重算未保存的前向激活，因此增加计算开销
B. 它会减少模型参数个数
C. 它主要通过压缩优化器状态来节省显存
D. 它可以显著减少训练时保存激活所需的显存

答案：A、D
难度：简单
考点：大模型—训练显存优化
解析：

A 正确：未保存的中间激活要在反向阶段重新计算，训练时间通常增加。
B 错误：模型结构和参数数量没有改变。
C 错误：优化器状态压缩属于低精度优化器、状态分片等技术解决的问题。
D 正确：少保存激活正是 Checkpointing 的核心收益。

17、关于大模型训练与推理显存优化，下列说法正确的是哪些？

A. PagedAttention 的核心用途是训练阶段重算激活
B. PagedAttention 可降低推理阶段 KV Cache 的内存碎片并支持灵活分配
C. Activation Checkpointing 通过重计算减少训练激活显存
D. 低位宽量化 KV Cache 可以降低推理缓存占用

答案：B、C、D
难度：中等
考点：大模型—显存优化
解析：

A 错误：PagedAttention 主要服务于推理阶段的 KV Cache 管理，不是激活重算技术。
B 正确：分页式分配减少连续大块内存需求和碎片，并便于共享物理块。
C 正确：Checkpointing 是典型的“以算换存”。
D 正确：KV 元素位宽降低后，每个 token 的缓存字节数随之减少。

18、关于 ResNet 中的 Shortcut（捷径连接），下列说法正确的是哪些？

A. 它为梯度提供更直接的传播路径，有助于缓解深层网络中的梯度消失和退化问题
B. 它要求每个残差分支都不使用非线性激活
C. 它只能用于图像分类中的卷积网络
D. 残差思想已广泛用于 MLP、CNN、RNN 等多类网络结构

答案：A、D
难度：中等
考点：深度学习—残差连接
解析：

A 正确：恒等捷径使信息和梯度能够沿较短路径传播，深层模型更易优化。
B 错误：残差分支内部可以包含卷积、线性层、归一化和非线性激活。
C 错误：残差连接并不局限于视觉任务。
D 正确：MLP、CNN、RNN 以及 Transformer 都广泛借鉴了残差思想。

19、在注意力机制中用余弦相似度替代未经缩放的点积，下列判断正确的是哪些？

A. 余弦相似度仍然完整保留了 Query 和 Key 的模长信息
B. 余弦值域受限，若没有合适的温度缩放，Softmax 分布可能过于平缓
C. 点积同时包含方向相似性与向量模长信息
D. 余弦相似度等价于先对两个向量做 L2 归一化再计算点积

答案：B、C、D
难度：中等
考点：深度学习—注意力/相似度
解析：

A 错误：归一化会去掉模长信息。
B 正确：余弦值被限制在 $[-1,1]$，直接送入 Softmax 可能缺少足够的 logit 动态范围，常搭配可学习温度。
C 正确：$q^Tk=\lVert q\rVert\lVert k\rVert\cos\theta$，既含夹角也含模长。
D 正确：$\cos(q,k)=\dfrac{q^Tk}{\lVert q\rVert\lVert k\rVert}$，就是归一化向量的点积。

20、关于多模态模型的训练与网络分支，下列说法正确的是哪些？

A. 对不同模态或任务分支进行梯度归一化，可以帮助平衡各分支的更新尺度
B. 多模态联合训练中可能出现某个模态梯度占主导的失衡现象
C. 对很大的正输入，Swish 的导数趋近于 $1$ D. 对部分冗余分支进行结构化裁剪可以降低计算量，但通常需要评估或微调以控制精度损失

答案：A、B、C、D
难度：中等
考点：多模态—训练平衡/激活函数/模型压缩
解析：

A 正确：梯度归一化或动态加权能缓解不同任务、模态梯度尺度差异。
B 正确：模态质量、损失尺度和收敛速度不同，都可能造成训练失衡。
C 正确：$\operatorname{Swish}(x)=x\sigma(x)$，当 $x\to+\infty$ 时 $\sigma(x)\to1$、$\sigma’(x)\to0$，故导数趋近 $1$。
D 正确：分支裁剪可以减少参数和计算，但裁剪后的模型通常需要验证，必要时再微调恢复性能。

第 1 题：MoE 动态路由

题目描述

某 Mixture of Experts（MoE）层包含 $E$ 个专家，需要依次处理 $N$ 个 token。每个 token 对每个专家都有一个路由分数。

对第 $i$ 个 token，先从全部专家中选出分数最高的 $K$ 个候选专家。候选顺序按以下规则确定：

路由分数高的专家在前；
分数相同时，专家编号小的在前。

随后按该顺序尝试把当前 token 路由给这 $K$ 个专家。每个专家最多接收 $C$ 个 token；若候选专家已经满载，则跳过该专家，不再为它分配当前 token，也不会从 Top-K 之外补选其他专家。专家容量彼此独立，同一个 token 可以被多个候选专家接收。

所有 token 必须严格按照输入顺序处理。处理结束后，第 $j$ 个专家的负载记为 $load_j$，定义负载惩罚：

\[P=\sum_{j=0}^{E-1}load_j^2.\]

请输出 $P$ 和所有专家的最终负载。

输入格式

第一行包含四个整数 $N,E,K,C$：

$1\le N\le10^4$；
$1\le E\le100$；
$1\le K\le E$；
$1\le C\le N$。

接下来 $N$ 行，每行包含 $E$ 个整数，第 $i$ 行第 $j$ 个数表示第 $i$ 个 token 对第 $j$ 个专家的路由分数。分数范围为 $0$ 到 $10^4$。

专家编号从 $0$ 到 $E-1$。

输出格式

第一行输出负载惩罚 $P$。

第二行输出 $E$ 个整数，依次表示 $load_0,load_1,\ldots,load_{E-1}$。

样例 1

输入

输出

9
1 2 2

前三个 token 依次使负载变为 $[0,1,1]$、$[1,2,1]$、$[1,2,2]$。处理最后一个 token 时，其 Top-2 专家 $1,2$ 均已满载，因此负载不变，$P=1^2+2^2+2^2=9$。

样例 2

输入

输出

13
2 2 1 2

最终负载平方和为 $2^2+2^2+1^2+2^2=13$。

思路分析

第一步：按 token 顺序模拟

容量约束会让后面的 token 受到前面分配结果影响，因此不能把 token 打乱或并行地独立决定最终负载。维护长度为 $E$ 的数组 loads，按照输入顺序逐行处理。

第二步：确定每个 token 的 Top-K

对专家编号 0...E-1 排序，排序关键字为 (-score, expert_id)。负分数实现分数降序，专家编号本身实现同分时编号升序。取排序后的前 $K$ 个编号即可。

第三步：逐个检查独立容量

遍历 Top-K 候选。如果 loads[expert] < C，就让该专家负载增加 $1$；否则直接跳过。这里不能在某个候选满载后从排名第 $K+1$ 的专家补位，因为题目只会尝试原始 Top-K。

第四步：计算平方和

所有 token 处理完毕后，直接累加 load * load。最坏情况下 $P$ 可能超过 32 位有符号整数范围，Python 整数可直接处理；使用其他语言时应使用 64 位整数。

题解代码

import sys

input = sys.stdin.readline

n, expert_count, top_k, capacity = map(int, input().split())
loads = [0] * expert_count

for _ in range(n):
    scores = list(map(int, input().split()))
    experts = sorted(
        range(expert_count),
        key=lambda expert: (-scores[expert], expert),
    )

    for expert in experts[:top_k]:
        if loads[expert] < capacity:
            loads[expert] += 1

penalty = sum(load * load for load in loads)
print(penalty)
print(*loads)

Top-K 最小堆写法

当 $K$ 远小于 $E$ 时，也可以扫描一行分数并只维护大小为 $K$ 的最小堆。为了让堆顶表示 Top-K 中“最差”的候选，堆元素使用 (score, -expert_id)：分数更低者更差；分数相同时，编号更大者更差。

import heapq
import sys

input = sys.stdin.readline

n, expert_count, top_k, capacity = map(int, input().split())
loads = [0] * expert_count

for _ in range(n):
    scores = list(map(int, input().split()))
    heap = []

    for expert, score in enumerate(scores):
        item = (score, -expert)
        if len(heap) < top_k:
            heapq.heappush(heap, item)
        elif item > heap[0]:
            heapq.heapreplace(heap, item)

    candidates = sorted(heap, key=lambda item: (-item[0], -item[1]))
    for _, negative_expert in candidates:
        expert = -negative_expert
        if loads[expert] < capacity:
            loads[expert] += 1

print(sum(load * load for load in loads))
print(*loads)

复杂度分析

时间复杂度：完整排序方案中，每个 token 对 $E$ 个专家排序，复杂度为 $O(NE\log E)$；容量模拟为 $O(NK)$。

空间复杂度：除输入的一行分数和排序结果外，只维护负载数组，额外空间复杂度为 $O(E)$。

若使用上文的大小为 $K$ 的堆，计算量可降为 $O(NE\log K+NK\log K)$，堆占用 $O(K)$。在本题 $E\le100$ 的范围内，完整排序已经足够稳妥且更易实现。

第 2 题：流水线连续划分

题目描述

有 $n$ 个任务按固定顺序组成一条流水线，第 $i$ 个任务的处理时间为 $time_i$。现在需要把这 $n$ 个任务划分为恰好 $p$ 个非空连续阶段，每个任务属于且只属于一个阶段，任务顺序不能改变。

每个阶段内任务处理时间之和不能超过上限 $T$。如果在任务 $i$ 与任务 $i+1$ 之间切分，需要支付通信代价 $comm_i$。

请在满足每个阶段时间上限的前提下，最小化全部 $p-1$ 个切口的通信代价之和。若不存在合法划分，输出 -1。

输入格式

第一行包含三个整数 $n,p,T$：

$1\le n\le1000$；
$1\le p\le n$；
$1\le T\le10^5$。

第二行包含 $n$ 个正整数 $time_1,time_2,\ldots,time_n$，其中 $1\le time_i\le100$。

第三行包含 $n-1$ 个整数 $comm_1,comm_2,\ldots,comm_{n-1}$，其中 $0\le comm_i\le10$。当 $n=1$ 时该行为空行。

输出格式

输出一个整数，表示最小通信代价；若无法恰好划分为 $p$ 个合法阶段，则输出 -1。

样例 1

输入

3 5
2 3 1 2
1 1 4

输出

一种最优划分为 $[2,2]\mid[3]\mid[1,2]$，两个切口的代价分别为 $comm_2=1$、$comm_3=1$，总代价为 $2$；每段处理时间都不超过 $5$。

样例 2

输入

2 3
2 2 2
1 1

输出

-1

任何包含两个任务的连续段处理时间都是 $4>3$。四个任务至少需要四段，无法恰好划分为两段。

思路分析

第一步：用前缀和判断一段是否合法

定义

\[prefix[i]=\sum_{j=1}^{i}time_j,\qquad prefix[0]=0.\]

区间任务 $k+1,\ldots,i$ 的总时间为 $prefix[i]-prefix[k]$，它能作为一个阶段，当且仅当

\[prefix[i]-prefix[k]\le T.\]

由于所有 time 都是正数，prefix 严格递增。对固定右端点 $i$，合法的前驱切分位置 $k$ 构成连续区间 $[L_i,i-1]$，其中 $L_i$ 是满足 $prefix[k]\ge prefix[i]-T$ 的最小位置，可用 bisect_left 求出。

第二步：写出朴素动态规划

令 $dp[s][i]$ 表示把前 $i$ 个任务恰好划分为 $s$ 个非空合法阶段的最小通信代价。最后一段若为任务 $k+1$ 到 $i$，则前 $k$ 个任务已经分为 $s-1$ 段，并且在任务 $k$ 后产生新切口，代价为 $comm_k$：

\[dp[s][i] =\min_{\substack{s-1\le k<i\\prefix[i]-prefix[k]\le T}} \left(dp[s-1][k]+comm_k\right).\]

这里数学下标中的 $comm_k$ 表示任务 $k$ 与 $k+1$ 之间的切口；在 Python 的 comm 数组中对应 comm[k - 1]。

第一段没有左侧切口，因此：

\[dp[1][i]= \begin{cases} 0,&prefix[i]\le T,\\ +\infty,&prefix[i]>T. \end{cases}\]

直接枚举 $s,i,k$ 的复杂度是 $O(pn^2)$，当 $n=p=1000$ 时最坏达到 $10^9$ 级别，无法接受。

第三步：把转移改写为滑动窗口最小值

对固定阶段数 $s$，转移候选值

\[dp[s-1][k]+comm_k\]

只由 $k$ 决定。随着右端点 $i$ 从小到大移动：

新的上界是 $i-1$，每次只新增一个候选 $k=i-1$；
因为前缀和递增，合法下界 $L_i$ 单调不减，过期候选只会从窗口左端退出。

使用最小堆保存三元组 (候选代价, k)。处理每个 $i$ 时：

若 dp_prev[i - 1] 可达，把新候选 $k=i-1$ 加入堆；
求出 $L_i$；
不断弹出堆顶中满足 $k<L_i$ 的过期候选；
若堆非空，堆顶代价就是 dp_cur[i]。

虽然某些过期元素不在堆顶时不会立刻删除，但它们不能影响当前最小值；一旦来到堆顶，再按下标判断并弹出即可。这是标准的惰性删除。

第四步：恰好划分为 $p$ 段

第 $s$ 轮只允许前驱 dp_prev[k] 已经恰好用了 $s-1$ 段；又因为每段非空，扫描范围从 $i=s$ 开始，新加入的 $k=i-1$ 自动满足 $k\ge s-1$。因此最终 dp_prev[n] 对应的是恰好 $p$ 段，而不是至多 $p$ 段。

如果某个单独任务满足 $time_i>T$，它不可能属于任何合法阶段，可以提前输出 -1。即使没有提前判断，DP 最终也会得到不可达状态。

题解代码

import bisect
import heapq
import sys

def solve():
    input = sys.stdin.readline

    n, stage_count, limit = map(int, input().split())
    times = list(map(int, input().split()))
    comm = list(map(int, input().split())) if n > 1 else []

    if max(times) > limit:
        print(-1)
        return

    prefix = [0] * (n + 1)
    for i, value in enumerate(times, start=1):
        prefix[i] = prefix[i - 1] + value

    infinity = 10**18

    # 恰好划分为 1 段。
    dp_prev = [infinity] * (n + 1)
    for i in range(1, n + 1):
        if prefix[i] <= limit:
            dp_prev[i] = 0

    for stages in range(2, stage_count + 1):
        dp_cur = [infinity] * (n + 1)
        min_heap = []

        # i 至少为 stages，保证每个阶段非空。
        for i in range(stages, n + 1):
            k = i - 1
            if dp_prev[k] < infinity:
                candidate_cost = dp_prev[k] + comm[k - 1]
                heapq.heappush(min_heap, (candidate_cost, k))

            lower = bisect.bisect_left(prefix, prefix[i] - limit, 0, i)
            while min_heap and min_heap[0][1] < lower:
                heapq.heappop(min_heap)

            if min_heap:
                dp_cur[i] = min_heap[0][0]

        dp_prev = dp_cur

    answer = dp_prev[n]
    print(-1 if answer == infinity else answer)


if __name__ == "__main__":
    solve()

正确性证明

引理 1： 对固定右端点 $i$，能够与 $i$ 组成合法最后一段的前驱位置恰好是 $[L_i,i-1]$。

证明： 最后一段 $k+1\ldots i$ 合法等价于 $prefix[k]\ge prefix[i]-T$。前缀和严格递增，因此满足该不等式的位置从第一个满足者 $L_i$ 开始，一直延续到 $i-1$。证毕。

引理 2： 计算 dp_cur[i] 时，堆顶是所有合法且可达前驱 $k$ 中 $dp_prev[k]+comm[k-1]$ 的最小值。

证明： 扫描到 $i$ 时，所有不超过 $i-1$ 的可达候选都已在其首次成为上界时入堆。根据引理 1，下标小于 $L_i$ 的候选已经非法；算法会持续删除所有位于堆顶的非法候选。未处于堆顶的非法元素不可能遮挡更小的合法值，若它成为堆顶也会被立即删除。因此最终堆顶恰为合法候选中的最小值。证毕。

定理： 算法输出把全部 $n$ 个任务恰好划分为 $p$ 个合法非空连续阶段的最小通信代价；不存在时输出 -1。

证明： 对阶段数归纳。$s=1$ 时，只有前 $i$ 个任务整体不超过 $T$ 才可达，且没有切口、代价为 $0$，初始化正确。假设 dp_prev[k] 已正确表示前 $k$ 个任务恰好划分为 $s-1$ 段的最优值。根据引理 2，算法枚举并取最小化了所有合法最后一段的前驱，同时加入唯一的新切口代价，所以得到的 dp_cur[i] 正是恰好 $s$ 段的最优值。归纳至 $s=p,i=n$ 即得结论；若状态仍为无穷大，说明没有任何合法划分，输出 -1。证毕。

复杂度分析

每一层 DP 中，每个前驱至多入堆一次、出堆一次，每次堆操作为 $O(\log n)$；每个状态还进行一次 $O(\log n)$ 的二分查找。

时间复杂度：$O(pn\log n)$。

空间复杂度：滚动数组、前缀和与最小堆均为 $O(n)$。

小结

选择题覆盖概率统计、经典机器学习、多模态训练及大模型显存优化，重点是理解每种技术解决的是训练问题还是推理问题
MoE 动态路由需要严格区分“先确定 Top-K”与“再检查容量”，满载候选不会触发 Top-K 之外的补选
流水线划分的朴素 DP 是 $O(pn^2)$；利用正处理时间带来的前缀和单调性，合法前驱形成滑动区间，可用最小堆优化到 $O(pn\log n)$

这篇文章有帮助吗？

| GitHub 留言