问题

有什么理论复杂但是实现简单的算法?

回答
好的,我们来聊聊那些听起来高深莫测,但真要上手去实现时,却意外地直接的算法。

很多时候,我们提到“算法”,脑子里会浮现出那些涉及深邃数学、复杂逻辑或者大规模计算的景象。比如深度学习里那些层层叠叠的神经网络,又或者图论里那些需要遍历所有可能路径的搜索算法。这些确实是算法的精彩之处,但它们的实现也往往伴随着巨大的工程量和专业知识门槛。

但今天我们想聊的,是另一种类型的算法。它们的核心思想可能极其精妙,解决的问题也可能非常棘手,然而一旦你把那个“精妙的核心”给剥离出来,剩下的实现步骤可能就直白得如同组装乐高。

我一直觉得,Kadane's Algorithm (卡德恩算法) 就是这样一个极好的例子。

这算法是用来解决一个经典的问题:“在一个一维数组(或者称为序列)中找出连续子数组的最大和”。

听起来是不是挺一般的?但想象一下,一个由正数、负数、零混合组成的数字串,你得从中找到一连串相邻的数字,它们的总和是所有可能的连续子数组中最大的。

举个例子:

`[2, 1, 3, 4, 1, 2, 1, 5, 4]`

你可能会手动去试:

`[1]` 的和是 1
`[3, 4]` 的和是 1
`[4, 1, 2, 1]` 的和是 6
`[2, 1, 3, 4, 1, 2, 1]` 的和是 2
`[4]` 的和是 4

等等。手动尝试很快就会变得混乱且低效,尤其是当数组非常长的时候。你需要考虑所有可能的起始点和所有可能的结束点,这在计算上是平方级的复杂度(O(n^2))。

Kadane's Algorithm 的精妙之处就在于它能用线性时间(O(n))解决这个问题,而且实现起来非常简洁。

它背后的核心思想是这样的:

当我们遍历数组时,我们总是尝试构建一个“当前正在考虑的子数组”。这个子数组的关键属性是:它要么是之前某个子数组的延续,要么是它自己本身(从当前位置开始一个新的子数组)。

更具体地说,让我们维护两个变量:

1. `current_max`: 这个变量记录的是以当前位置结尾的连续子数组的最大和。
2. `global_max`: 这个变量记录的是到目前为止我们找到的全局连续子数组的最大和。

现在来看怎么用这两个变量来“迭代”整个数组:

当我们处理数组中的每一个元素 `x` 时,我们有两条路可以选择来形成以 `x` 结尾的最大和子数组:

选择 1:将 `x` 加入到以前面的元素结尾的最大和子数组中。 也就是说,这个新子数组的和是 `current_max + x`。
选择 2:抛弃之前所有的子数组,从 `x` 本身开始一个新的子数组。 也就是说,这个新子数组的和是 `x`。

Kadane's Algorithm 的智慧在于,它知道我们只需要选择这两者中较大的那个来更新 `current_max`。所以,对于当前的元素 `x`,新的 `current_max` 就是 `max(x, current_max + x)`。

为什么这个简单规则有效?

考虑一下:如果以当前位置 `i1` 结尾的最大和 `current_max` 是负数,那么当我们遇到下一个元素 `x`(即位置 `i` 的元素)时,将 `x` 加入一个负数的前缀只会让总和变小。在这种情况下,从 `x` 开始一个全新的子数组 (`x`) 显然比 `current_max + x` 要好。如果 `current_max` 是正数,那么加入 `x` 可能会继续增大总和,或者在 `x` 是负数的情况下使其减小,但这个减小可能是值得的,因为它可能使得后续的元素能够构成一个更大的总和。核心是,`current_max` 总是维护着以当前位置结尾的最优解。

而 `global_max` 的更新则更直接:在每次更新完 `current_max` 之后,我们只需要比较一下当前的 `current_max` 和之前记录的 `global_max`。如果 `current_max` 更大,我们就更新 `global_max`。

算法流程总结如下:

1. 初始化 `global_max` 和 `current_max` 为数组的第一个元素。
2. 从数组的第二个元素开始遍历(索引 `i` 从 1 开始)。
3. 对于当前元素 `array[i]`:
更新 `current_max` 为 `max(array[i], current_max + array[i])`。
更新 `global_max` 为 `max(global_max, current_max)`。
4. 遍历结束后,`global_max` 就是连续子数组的最大和。

现在,我们来聊聊它的“实现简单”这一面。

如果你用 Python 来写,它可能就几行代码的事:

```python
def max_subarray_sum(arr):
if not arr:
return 0 或者抛出异常,取决于需求

global_max = arr[0]
current_max = arr[0]

for i in range(1, len(arr)):
current_max = max(arr[i], current_max + arr[i])
global_max = max(global_max, current_max)

return global_max

示例用法
my_array = [2, 1, 3, 4, 1, 2, 1, 5, 4]
print(f"The maximum subarray sum is: {max_subarray_sum(my_array)}") 输出: The maximum subarray sum is: 6
```

这就是全部了。没有复杂的嵌套循环,没有递归的深度,没有需要维护的数据结构(比如堆、栈等),甚至连条件判断都非常直接。你只需要两个变量,一个循环,以及一次简单的比较和赋值操作。

为什么我们会说它“理论复杂”?

“理论复杂”往往体现在它的 背后的证明 和 思考的深度。

为什么 `max(array[i], current_max + array[i])` 是正确的? 这个决策点的背后,隐藏着动态规划的思想。我们正在利用“最优子结构”和“重叠子问题”。“最优子结构”指的是,一个问题的最优解包含了其子问题的最优解。在这里,以当前位置 `i` 结尾的最大和子数组,要么是单独的 `array[i]`,要么是之前以 `i1` 结尾的最大和子数组加上 `array[i]`。如果以 `i1` 结尾的最大和子数组不是以 `i1` 结尾的“最优”子数组,那么它也不能帮助我们构建以 `i` 结尾的“最优”子数组。这就是动态规划的核心思考方式。
为什么线性时间复杂度是最优的? 要确定整个数组中连续子数组的最大和,你至少得“看”到每一个元素一次,对吧?因为任何一个元素都可能是一个潜在的单元素最大子数组,或者它可能是构成一个更大子数组的关键部分。因此,至少需要 O(n) 的时间。Kadane's Algorithm 实现了这一点。
如何处理全负数数组? 如果数组全是负数,比如 `[5, 1, 3]`,那么最大的连续子数组和就是最大的那个负数本身(在这里是 `1`)。Kadane's Algorithm 也能正确处理。初始时 `global_max = 5`, `current_max = 5`。
处理 `1`:`current_max = max(1, 5 + 1) = max(1, 6) = 1`。`global_max = max(5, 1) = 1`。
处理 `3`:`current_max = max(3, 1 + 3) = max(3, 4) = 3`。`global_max = max(1, 3) = 1`。
最终结果是 `1`,正确。

它的理论严谨性体现在它如何巧妙地避开了 O(n^2) 的蛮力搜索,而是通过一个“贪婪”的局部决策(总是选择当下最好的延续或重开始)来达到全局最优。这种将局部最优决策推广到全局的思路,在很多算法设计中都非常强大。

所以,Kadane's Algorithm 就像一位穿着朴素但思想深邃的老者,你可能一眼看去觉得他没什么特别,但一旦你听他讲几句话,就会发现他脑子里装着整个宇宙的智慧。它的实现如此简洁,以至于在第一次接触时,你会怀疑“就这么简单吗?”但它确实就是这么简单,却又如此强大。这大概就是“理论复杂,实现简单”的魅力所在吧。

网友意见

user avatar

提名MCMC(Markov Chain Monte Carlo),用于从一个目标分布 中抽样。通常抽样的目的是为了计算一个积分,在统计中最为常用的例子就是贝叶斯了。

可以毫不夸张的说,MCMC算法拯救了贝叶斯统计学派。

实现有多简单呢?MCMC中最为通用的一个算法是Metropolis-Hastings算法,非常简单:

其中 为一个工具分布,通常设置为对称的即 ,最简单的方法是设定一个随机游走: 。

比如,一个最简单的随机游走的M-H算法的函数:

       ##随机游走的MCMC算法,输入: ##    N_samples  : 抽样次数 ##      pai(x)   : 目标密度函数 ##   q_sampler(x): 给定x,从q中抽样的函数 ##      x0       : 初始值 def MH_RW(N_samples, pai, q_sampler, x0):     X=[]     x=x0     for i in range(N_samples):         y=q_sampler(x)         rho=min(1,pai(y)/pai(x))         if nprd.uniform()<=rho:             X.append(y)             x=y         else:             X.append(x)     return X     

就这么简单

理论有多复杂呢?

MCMC构造了一条马尔可夫链,可以证明在适当的条件下,这个马尔可夫链的平稳分布就是 ,但是这个马尔可夫链不是最简单的离散状态空间的马尔可夫链,而是一个一般状态空间上的(至少是 的状态空间)一个马尔可夫链。对于离散状态的马尔可夫链,遍历性、常返性、周期性之类的还算是比较容易定义的(虽然本科非数学专业的可能已经有一定接受难度了),对于一般状态空间上的马尔可夫链的遍历性,至少离开测度都很难定义常返性了。

总之,挺难的。

user avatar

提名并查集。在《算法导论》中被称为“不相交集合森林”。

没人能否认并查集实现简单(除非毒瘤出题人进行毒瘤扩展),因为其核心函数一行就可以实现。

       int findSet(int x) {     return par[x] == x ? x : par[x] = findSet(par[x]); } // par数组中,par[x]表示结点x的父结点。若x为根结点,par[x] = x。      

但当初学习时并没有深入思考其复杂度,只是简单接受了“近似O(1)”的这个结论。

然而这个复杂度分析比实现要复杂得多。后文主要着眼于复杂度分析,假设读者对并查集有一定了解,至少知道这玩意是啥。

以下需要对并查集有基本的了解。

一.并查集简述(回顾)

并查集是一个森林,由许多棵有根树组成,每棵树都表示一个集合,树的一个结点表示一个元素。这实际上就是并查集的精髓,两个元素所对应的结点在同一棵树中,意味着两个元素在同一个集合中,反之亦然。

而并查集的功能(操作),就如它的名字:合并和查询

  • 合并 unionSet:把森林中的两棵树合并为一棵树,也就是合并两个集合。
  • 查询 findSet:查询某个结点所在的树的根结点。通过比较两次查询操作,我们就可以得知两个结点在不在同一棵树中,实际上也就是得知两个元素在不在同一个集合中。

二.实现方式及复杂度分析

并查集有多种实现方式(优化方式),比如按秩合并路径压缩。上面的代码就采用了路径压缩,相信OIer们都看得懂。findSet函数经过一系列递归,最后的返回值是这棵树的根结点,于是par[x] = findSet(par[x])这句代码就将结点x的父结点标记为树的根,从而实现了路径的压缩。

一步一步来。

以下假设n为总结点数,m为操作数。初始情况下,我们有n棵只有一个结点的树。

1.最朴素的(没人写的)并查集

最朴素的并查集,也就是没有按秩合并,也没有路径压缩。这就导致我们可以构造出一组数据,在n次合并之后得到一个长度为n的链,使得这个并查集的时间复杂度非常高。这其实和二叉查找树(BST)有一点相似,都可以通过构造数据使树退化一条链。为了防止这种退化,BST被改进为平衡二叉树(BBST);而并查集则通过种种启发式策略进行优化。

如果树退化为链,我们对叶结点进行查询/合并操作,那就需要遍历整个树(链),复杂度达到了 ,高的可怕。

2.按秩合并的并查集

按秩合并,略显晦涩的名字,但它的英文union by rank很容易理解。秩(rank)的定义并不固定,有的人定义树的大小即结点数量(size)为秩,有的人定义树的高度(height)为秩。但无论如何,它们合并操作的思想是一样的,如下:

       void unionSet(x, y) {     x = findSet(x); y = findSet(y); // 找到它们的根     if(rank[x] > rank[y]) par[y] = x;  // 数组rank储存结点的秩,可以是size或者height     else                  par[x] = y;     update(rank, x, y); // 自由发挥啦,是size改size,是height改height }      

我们先分析以高度height为秩的并查集。

  • 引理1:以高度height为秩的按秩合并并查集中,每棵树的高度最多为 ,且可达到 (此处及此后均假设 以2为底)

证明:首先显然,被我们合并的两棵树,当且仅当高度相同时,合并后得到的树高度会变化为原高度+1;其余情况,合并得到的树高度与原来两棵树中最高的那棵高度相同。因此,想得到一棵高度为的树,就必须由两棵高度为 合并得到……一直推下去,我们至少需要 个结点才行。而要得到高度为 的树,就需要 个结点。显然 ,证明完毕。

这样,在一系列合并之后,我们就可以使查询操作的最坏情况达到 。

更进一步,我们分析以大小size为秩的并查集。一个显而易见的思路是建立size和height之间的关系,从而间接得到复杂度。

  • 定义
  • 引理2单调性:对任意 ,有 ,这是显然的。
  • 推论3:若 是使 的最小的 ,则 是使 的最小的 。用引理2反证可得。
  • 推论4: 。数学归纳法,显然 ,由推论3可得推论4。

推到推论4,我们已经得到size和height的关系。

于是有结论:对于按秩合并的并查集,不论以size为秩,还是以height为秩,单次操作最坏情况都是 ,m次操作的总复杂度也就是 .

到这为止,一切都并不很复杂。但一旦涉及到路径压缩,分析的困难就增加了。因为路径压缩有多种启发式策略,其本身还可以和按秩合并结合。这方面的很多成果都由Tarjan先做出来的,其中使用了摊还分析。

正在治疗懒癌,活下来再更新……

user avatar

Batch Normalization

实现有多简单,标准化+反标准化。

理论有多复杂,到目前为止,都没有很好的理论证明,绝大多数文章还停留在实验阶段。

据我所知,BN的解释经历了这么几个主要阶段:

  1. 避免Internal Covariate Shift

原始的BN论文给出的解释是BN可以解决神经网络训练过程中的ICS(Internal Covariate Shift)问题,所谓ICS问题,指的是由于深度网络由很多隐层构成,在训练过程中由于底层网络参数不断变化,导致上层隐层神经元激活值的分布逐渐发生很大的变化和偏移,而这非常不利于有效稳定地训练神经网络。

2. 平滑loss landscape

BN效果好是因为BN的存在会引入mini-batch内其他样本的信息,就会导致预测一个独立样本时,其他样本信息相当于正则项,使得loss曲面变得更加平滑,更容易找到最优解。相当于一次独立样本预测可以看多个样本,学到的特征泛化性更强,更加general。

这个结论在之前的How Does Batch Normalization Help Optimization?文章中明确提出来过。

图中展示了用L-Lipschitz函数来衡量采用和不采用BN进行神经网络训练时两者的区别,可以看出未采用BN的训练过程中,L值波动幅度很大,而采用了BN后的训练过程L值相对比较稳定且值也比较小,尤其是在训练的初期,这个差别更明显。这证明了BN通过参数重整确实起到了平滑损失曲面及梯度的作用。

3. 导致Information Leakage

在最近很火的对比学习中,如果在mini-batch内计算BN统计量,就会导致预测一个独立样本时,会引入其他mini-batch样本的信息,造成信息泄露,骗过模型。

如图所示,当使用random采样的mini-batch统计量时,验证误差会增加,当使用population统计量时,验证误差会随着epoch的增加逐渐增大,导致明显的过拟合,验证了BN信息泄露问题的存在。

即便是在理论如此匮乏的情况下,BN也孕育出了许许多多的变体,比如GN、LN、IN等等。

batch normalization可以说是深度学习时代的black art,或者说是necessary evil。


Reference

[1] Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift

[2] How Does Batch Normalization Help Optimization?

[3] Rethinking "Batch" in BatchNorm

类似的话题

  • 回答
    好的,我们来聊聊那些听起来高深莫测,但真要上手去实现时,却意外地直接的算法。很多时候,我们提到“算法”,脑子里会浮现出那些涉及深邃数学、复杂逻辑或者大规模计算的景象。比如深度学习里那些层层叠叠的神经网络,又或者图论里那些需要遍历所有可能路径的搜索算法。这些确实是算法的精彩之处,但它们的实现也往往伴随.............
  • 回答
    血与火的淬炼,精神的传承:抗美援朝对当下中国处理国际关系的启示当我们回望那段烽火连天的岁月,抗美援朝战争留给我们的不仅仅是历史的尘埃,更是深入骨髓的精神力量。这股力量,在今天错综复杂的国际关系格局下,为我们如何正确认识、理解和处理问题,提供了宝贵而深刻的启示。它不是一句空洞的口号,而是经过血与火洗礼.............
  • 回答
    控制理论、系统工程和复杂性科学,这三者之间并非孤立存在,而是有着深刻而紧密的内在联系,共同描绘着我们理解和改造世界的多维度视角。要深入理解它们的关系,不妨从各自的本质出发,再逐步剖析它们交织融合之处。控制理论:精准的驾驭与引导控制理论,顾名思义,它的核心在于“控制”。它研究的是如何通过对一个系统的输.............
  • 回答
    高考失利,复读还是择校,这是摆在许多考生和家长面前的难题。这两种选择都各有优劣,没有绝对的好坏,关键在于结合自身情况,做出最适合自己的决定。下面我将从多个维度详细分析这两种选择,并分享一些经验,希望能帮助你理清思路。 一、 复读:是“再战一次”还是“重复过去”?复读的本质是给自己一次“重来”的机会,.............
  • 回答
    凌迟,又称“千刀万剐”,是中国历史上一种极其残忍的死刑执行方式。它通过在受刑者身上分多次割下小块肉,直至最终死亡。这种刑罚的恐怖之处在于其极度的延长和持续的痛苦,以及对受刑者身体和精神的双重折磨。要理论上找到“痛苦堪比凌迟”的状况,我们需要从多个维度来考量,包括但不限于:1. 极端且持续的身体疼痛:.............
  • 回答
    关于密码子三联体如何形成,这是一个生物学中最基本也最迷人的问题之一,它涉及到生命信息如何从基因编码的核苷酸序列,转化为细胞功能所必需的蛋白质。这个过程并非一蹴而就,而是经过了漫长而精密的演化过程。虽然我们无法确切地“回到过去”来观察这个形成过程的每一个细节,但通过对现存生物体遗传密码的研究以及分子生.............
  • 回答
    神经网络中的Warmup策略之所以有效,并且有相应的理论解释,主要是为了解决在训练初期,模型参数变化剧烈,导致训练不稳定甚至发散的问题。下面我们来详细阐述其有效性、理论解释以及一些相关的细节。 Warmup策略为什么有效?Warmup策略的核心思想是:在训练初期,逐渐增加学习率,而不是一开始就使用一.............
  • 回答
    我理解你想探讨的是人声在演唱时,那种细微的音高浮动和颤音(vibrato)为何会让人觉得充满感情,而绝对精准的音高反而会显得生硬怪异。这背后确实牵涉到很多音乐理论和人类感知心理学层面的知识,咱们来好好聊聊。1. 为什么“不那么完美”的音高会更好听?—— 人声的自然属性与情感表达首先,咱们得明白,人声.............
  • 回答
    好的,我们来聊聊一些在科学和数学领域留下深刻印记的著名理论和定理。我尽量用生动的方式来讲述,希望你能感受到它们在推动人类认知边界方面的重要作用,而不是冰冷的公式堆砌。1. 万有引力定律(Newton's Law of Universal Gravitation)提到牛顿,很多人会想起那个被苹果砸到脑.............
  • 回答
    当然!合同理论是一个非常基础且重要的经济学分支,它解释了为何以及如何形成合同,以及合同的条款是如何确定的。它在现代社会中有着广泛而深入的应用。下面我将为您详细介绍科普类书籍推荐以及合同理论的实际应用。 科普类书籍推荐要找一本真正意义上的“科普”合同理论的书籍可能稍微有些挑战,因为合同理论本身是偏向理.............
  • 回答
    学习质数理论,乍一听似乎是高深的数学概念,离我们日常生活很远。但实际上,它在现代社会的应用是相当广泛且关键的,尤其体现在信息安全、密码学以及一些算法的设计上。要说它的“实用之处”,我们需要一点点深入地去剖析。首先,咱们得明白质数是什么。简单来说,质数就是大于1的自然数,它除了1和它本身之外,不能被其.............
  • 回答
    金庸武侠世界博大精深,吸引了无数读者,而其中许多读者由于对剧情的深入钻研、对人物的喜爱以及对武侠世界的无限想象,发展出了一些非常“稀奇古怪”的理论。这些理论或许缺乏绝对的证据支持,但往往充满了趣味性和脑洞,也反映了读者们对作品的热情和创造力。以下是一些金庸读者中比较有代表性的稀奇古怪理论,我会尽量详.............
  • 回答
    布热津斯基的“奶头乐”(Tittytainment)理论,虽然名字听起来有些戏谑和粗俗,但其背后蕴含着对当代社会政治和大众心理深刻而又发人深省的洞察。它不是一个严谨的学术理论,而是一种极具前瞻性和警示性的观察和预测。要理解“奶头乐”理论的深层内涵,我们需要将其置于布热津斯基所处的时代背景以及他对于全.............
  • 回答
    没有实证研究基础的心理学理论,听起来似乎是缺乏根基的空中楼阁,仿佛无法在现实世界中落地生根。但仔细审视,它们并非一无是处,反而可能在某些特定层面上,为我们理解人类心智提供独特的视角和重要的价值。这些价值,如同未经雕琢的原石,虽然不闪耀,但其内在的潜力不容小觑。首先,它们是思想的起点和探索的火种。 许.............
  • 回答
    谢作诗教授作为一位经济学者,其理论研究和观点在学术界和社会上都引起过广泛的讨论,也并非没有受到质疑和批评。要理解这些批评,我们需要深入探究他理论的基石以及这些基石可能存在的局限性。首先,谢教授的许多观点倾向于市场机制在资源配置中的决定性作用,并且对政府干预的必要性和有效性持较为审慎的态度。这种立场本.............
  • 回答
    这问题触及了经济学、社会学乃至哲学的一些根本之处,而且一旦深入下去,就会发现它远比表面上看起来要复杂得多。简单来说,一个阶层秉持对自己有利的经济理论,本身算不上绝对的“错”,但却必然带来深刻的社会结构性问题,并且可能从根本上扭曲对“经济学”这门学科的理解和实践。让我们一层层剥开来看。一、 为什么会“.............
  • 回答
    古德里安的“闪击战”与图哈切夫斯基的“大纵深攻击”理论,同为二战前苏德两国对现代战争模式进行的深刻思考与实践的产物,都旨在突破传统战线束缚,实现对敌人的决定性打击。然而,它们在核心思想、侧重点以及具体战术运用上存在显著差异。相同点: 打破静态战争的束缚,追求主动与机动: 这是两者最核心的共同点。.............
  • 回答
    控制理论是一门非常重要的学科,它的应用范围极其广泛,可以说渗透在我们生活的方方面面。简单来说,控制理论研究的是如何让一个系统(我们称之为“被控对象”)按照我们期望的方式运行。 想象一下,你想要让一辆汽车保持在车道上行驶,或者让房间的温度保持恒定,这些都需要控制。下面我将从多个角度,详细阐述控制理论的.............
  • 回答
    温铁军教授的理论,尤其是其关于“三农问题”和中国经济发展的论述,在中国学界和公众中引起了广泛的讨论和争议。他的理论体系庞大,内容丰富,涵盖了经济史、农业政策、金融体制、制度经济学等多个领域。尽管其理论具有深刻的洞察力和重要的现实意义,但也存在一些被批评者指出的缺陷。以下我将尽量详细地梳理温铁军理论中.............
  • 回答
    好的,我们来聊聊剩余价值理论和劳动价值论,这两者可是马克思主义经济学中的核心概念,而且关系非常密切。要讲清楚它们,咱们得从根本上剖析一下。一、 劳动价值论:一切价值的源泉首先,咱们得说说劳动价值论。这理论的核心观点很简单,但影响深远: 商品的价值是由生产它所耗费的社会必要劳动时间决定的。 啥意思.............

本站所有内容均为互联网搜索引擎提供的公开搜索信息,本站不存储任何数据与内容,任何内容与数据均与本站无关,如有需要请联系相关搜索引擎包括但不限于百度google,bing,sogou

© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有