证明

核心思想就是找到一个转换，可以通过点积操作将位置信息注入，即： \[<f_q\left(x_m,m\right),f_k\left(x_n,n\right)>=g\left(x_m,x_n,m-n\right)\] 而通过复数的一些性质，找到了满足上述操作的转换：

\[\begin{aligned} &f_{q}\left(\boldsymbol{x}_{m},m\right)=\left(\boldsymbol{W}_{q}\boldsymbol{x}_{m}\right)e^{im\theta} \\ &f_{k}\left(\boldsymbol{x}_{n},n\right)=\left(\boldsymbol{W}_{k}\boldsymbol{x}_{n}\right)e^{in\theta} \\ &g\left(\boldsymbol{x}_{m},\boldsymbol{x}_{n},m-n\right)=\mathrm{Re}\left[\left(\boldsymbol{W}_{q}\boldsymbol{x}_{m}\right)\left(\boldsymbol{W}_{k}\boldsymbol{x}_{n}\right)^{*}e^{i(m-n)\theta}\right] \end{aligned}\] 可以发现g函数中存在相对位置信息。 欧拉公式：\(e^{ix}=\cos x+i\sin x\)

KV cache

LLM推理过程分为Prefill和Decode两个阶段，其中Prefill阶段会对Prompt中所有的token做并行计算，得到Prompt中所有Tokens的KV Cache以及计算得到首Token。Prompt阶段Token计算得到的KV Cache会保存下来，留给Decode阶段复用，Decode阶段是一个自回归过程，每decode一个新的Token，都需要用到所有之前计算得到的KV Cache来计算当前query token的Attention。因此，当输出长度越来越大或者context很长时，KV Cache将会占用大量的显存。如何优化KV Cache的显存占用，一直都是LLM推理的核心主题之一。

Low-Rank Adaption (LoRA)，即“低秩适配”，实现了预训练模型的参数高效微调，且不会增加模型的推理延迟。 ## 内在维度 2020年，A. Aghajanyan等人研究了这一现象，发现预训练模型存在一个较低的”内在维度”,使用少量样本微调时，实际上是在更新低维空间中的参数。把预训练模型的全部参数看成一个D维参数向量，记为\(\Theta^\mathrm{(D)}\),模型的原始参数为\(\Theta_0^\mathrm{(D)}\),设\(\Theta^{(d)}\)是d维子空间中的一个向量，d<D,利用一个固定的D*d映射矩阵P 把d维空间中的向量映射到D维空间，\(\Theta^{(\mathrm{D})}\)可写为：

MoE 的思想类似于集成学习中的 Ensemble Learning。MoE 作用于原本 transformer 模型的 MLP 层，即：

图片来自于Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity 论文。

总结来说，在混合专家模型 (MoE) 中，我们将传统 Transformer 模型中的每个前馈网络 (FFN) 层替换为 MoE 层，其中 MoE 层由两个核心部分组成: 一个路由器（或者叫门控网络）和若干数量的专家。

Problem:

思路

注意拓扑排序最好是邻接表（哈系表实现），并用队列处理后续入度为0的点

解题方法

描述你的解题方法

复杂度

时间复杂度:

添加时间复杂度, 示例： \(O(n)\)

空间复杂度:

添加空间复杂度, 示例： \(O(n)\)

Problem:

思路

讲述看到这一题的思路

解题方法

描述你的解题方法

复杂度

时间复杂度:

添加时间复杂度, 示例： \(O(n)\)

空间复杂度:

添加空间复杂度, 示例： \(O(n)\)

Code

跳跃游戏

Problem:

思路

讲述看到这一题的思路

解题方法

描述你的解题方法

复杂度

时间复杂度:

添加时间复杂度, 示例： \(O(n)\)

空间复杂度:

添加空间复杂度, 示例： \(O(n)\)

Code

```Python3 []

# 跳跃游戏ii

# 划分字母区间

[763. 划分字母区间 - 力扣（LeetCode）](https://leetcode.cn/problems/partition-labels/description/?envType=study-plan-v2&envId=top-100-liked)
本题预处理完毕后思路和跳跃游戏2类似，当然也可以使用合并区间的思路来，都是贪心算法。
## Code
```python
class Solution:

    def partitionLabels(self, s: str) -> List[int]:

        from collections import defaultdict

        d = defaultdict(list)

        for i, char in enumerate(s):

            d[char].append(i)

        # 也可以考虑合并区间做了，下面的解法类似跳跃游戏2

        res = []

        start = 0

        max_jump = 0

        for i, char in enumerate(s):

            max_jump = max(max_jump, d[char][-1])

            if i == max_jump:

                res.append(i - start + 1)

                start = i + 1

                max_jump = 0

        return res

41. 缺失的第一个正数 - 力扣（LeetCode） 空间复杂度o(n)很好想，但o(1)不好想，还是个408考研真题

注意O(n) == O(2n)，即相较于边遍历边判断，还是遍历两次更加方便且不会有太多损失。类似思想：73. 矩阵置零 - 力扣（LeetCode）

题目地址 # 思路 通过前缀和+哈希表，并有简单的数学变换。前缀和即 \(y[i]=y[i-1]+x[i]\) 类比于accumlate函数，注意前缀和思想也可以应用为“前缀积、后缀和、后缀积”等思想。238. 除自身以外数组的乘积 - 力扣（LeetCode） > 使用前缀和的方法可以解决这个问题，因为我们需要找到和为k的连续子数组的个数。通过计算前缀和，我们可以将问题转化为求解两个前缀和之差等于k的情况。 >假设数组的前缀和数组为prefixSum，其中prefixSum[i]表示从数组起始位置到第i个位置的元素之和。那么对于任意的两个下标i和j（i < j），如果prefixSum[j] - prefixSum[i] = k，即从第i个位置到第j个位置的元素之和等于k，那么说明从第i+1个位置到第j个位置的连续子数组的和为k。 通过遍历数组，计算每个位置的前缀和，并使用一个哈希表来存储每个前缀和出现的次数。在遍历的过程中，我们检查是否存在prefixSum[j] - k的前缀和，如果存在，说明从某个位置到当前位置的连续子数组的和为k，我们将对应的次数累加到结果中。 这样，通过遍历一次数组，我们可以统计出和为k的连续子数组的个数，并且时间复杂度为O(n)，其中n为数组的长度。 # 代码

题目地址 # 思路 通过前缀和+哈希表，并有简单的数学变换。前缀和即 \(y[i]=y[i-1]+x[i]\) 类比于accumlate函数，注意前缀和思想也可以应用为“前缀积、后缀和、后缀积”等思想。238. 除自身以外数组的乘积 - 力扣（LeetCode） > 使用前缀和的方法可以解决这个问题，因为我们需要找到和为k的连续子数组的个数。通过计算前缀和，我们可以将问题转化为求解两个前缀和之差等于k的情况。 >假设数组的前缀和数组为prefixSum，其中prefixSum[i]表示从数组起始位置到第i个位置的元素之和。那么对于任意的两个下标i和j（i < j），如果prefixSum[j] - prefixSum[i] = k，即从第i个位置到第j个位置的元素之和等于k，那么说明从第i+1个位置到第j个位置的连续子数组的和为k。 通过遍历数组，计算每个位置的前缀和，并使用一个哈希表来存储每个前缀和出现的次数。在遍历的过程中，我们检查是否存在prefixSum[j] - k的前缀和，如果存在，说明从某个位置到当前位置的连续子数组的和为k，我们将对应的次数累加到结果中。 这样，通过遍历一次数组，我们可以统计出和为k的连续子数组的个数，并且时间复杂度为O(n)，其中n为数组的长度。 # 代码