← 目录 · 第一卷 Hello World · ~3.3K 字

// 第12章 O(n²) 的困境

外门月度考核——排序试炼塔。

每月初五,开源宗会开启一座名为"排序塔"的试炼设施。塔共九层,每层设有一组"乱序灵兽"——由术式构建的虚拟对手,实力从弱到强依次排列。

考核规则:使用排序类术式击败每一层的灵兽,用时越短排名越高。排序术是修炼界最基础的战斗流派之一,开源宗将其作为外门弟子的核心考核项目。

叶辰入门已经半月。

在这半个月里,他疯狂地在碑林补课,将通常需要三个月完成的基础依赖压缩到了两周。代价是他的术式基础如同一座豆腐渣工程——NULL每天都在给他列出一长串"已知但未修复的bug清单"。

但他的冒泡排序掌在实战和持续修炼中已经从60%的完成度提升到了85%。

入门考核时那种吞入、排序、释放的三段式流程已经变得流畅了许多。

"冒泡排序掌,当前版本:v2.3。"NULL在考核前进行了最后一次评估,"时间复杂度O(n²),空间复杂度O(1),稳定性:良好。在码农境三阶的算力水平下,可有效应对码农境五阶及以下的单体目标。"

"够通过月考吗?"

"排序塔的前三层问题不大。第四层开始,灵兽的攻击频率会急剧上升——冒泡排序的O(n²)时间复杂度将成为致命瓶颈。"

叶辰沉默了。

他知道O(n²)意味着什么——当需要排序的"元素"(也就是敌人的攻击)数量增加时,冒泡排序掌需要处理的运算量会呈平方级增长。十个攻击需要一百次操作,二十个攻击需要四百次,三十个攻击需要九百次……

而快速排序——O(n log n)——十个攻击只需要约三十三次操作,二十个约八十六次,三十个约一百四十七次。

差距是碾压级的。


排序塔内。

第一层。

五只低级乱序灵兽。

叶辰的冒泡排序掌吞入、排序、释放——三个循环,干净利落。灵兽碎裂为数据碎片。

用时:四十七秒。

第二层。

八只中级乱序灵兽。

冒泡排序掌的效率开始下降——八个攻击意味着更长的排序循环。叶辰被其中一只灵兽的尾击扫到了肩膀,但最终完成了清场。

用时:两分十三秒。

第三层。

十二只灵兽。

叶辰明显感觉到了吃力。冒泡排序掌的内部循环在处理十二个目标时变得极其缓慢——每一次"比较"都需要消耗一定的算力和时间,而十二个目标意味着他需要进行大约一百四十四次比较操作。

在他缓慢排序的过程中,灵兽们的攻击不会停下来等他。

他被打中了三次才完成清场。

用时:五分零八秒。

第四层。

十八只灵兽。

冒泡排序掌的O(n²)瓶颈彻底爆发。

十八个目标——三百二十四次比较操作。叶辰的术式在高负荷下开始卡顿,反应速度大幅下降。灵兽们从四面八方涌来,他疲于应付,冒泡排序掌的吞入机制已经无法同时处理这么多攻击流。

他被连续击中五次后,排序塔的安全机制强制将他传送了出来。

"闯关失败。最终成绩:三层。"

叶辰站在排序塔外,大口喘气。

三层——在这一期的月度考核中,是什么水平?

他抬头看了一眼结果碑上的实时排名。

排序试炼塔 - 本月成绩榜

第1名:赵空明(内门)    九层通关   用时:3分42秒
第2名:林玄(内门)      八层       用时:6分18秒
第3名:苏沐橙(外门)    七层       用时:8分55秒
...
第47名:叶辰(外门)     三层       用时:7分21秒
第48名:周远(外门)     三层       用时:8分04秒
第49名:许锋(外门)     二层       用时:5分11秒

倒数第三。

和入门考核一样。

九层通关,用时三分四十二秒——赵空明的成绩像一座不可逾越的高山压在排名榜的最顶端。他的快排剑法,O(n log n)的时间复杂度,在处理大量目标时展现出了碾压性的效率优势。

叶辰盯着那个数字看了很久。

"看够了吗?"

一个温润如玉的声音从背后传来。

叶辰转身。

赵空明站在他身后三步外,一袭白衣如雪,嘴角挂着那种叶辰已经熟悉的、恰到好处的微笑。

"叶辰师弟,三层的成绩——在外门新弟子中不算太差。"

他的语气温和、体贴,像是一个慷慨的学长在鼓励后辈。

但叶辰注意到了他话中的停顿——"不算太差"前面有一个极其微小的间隙。就像一行代码中刻意留白的空格——不影响编译,但改变了语义。

"不算太差"的意思其实是——不值一提。

"谢谢赵师兄。"叶辰不卑不亢地回答。

"冒泡排序掌——很经典的入门术式。"赵空明微微偏头,像是在欣赏一件有趣但廉价的古董,"不过你应该也看到了——O(n²)的时间复杂度在高层对抗中是致命的。当敌人的数量或攻击频率超过一定阈值后,冒泡排序会被自身的效率拖垮。"

他的目光从排名榜上自己的名字移到叶辰的名字,又移回来。

"如果你想在下个月的考核中有所提升,建议学习更高效的排序术式。源码碑林里有完整的快排剑法教程——虽然对码农境三阶来说有些困难,但以你的悟性,应该可以尝试。"

微笑。温和。体贴。

每一个字都是善意的建议。

但叶辰从那双没有跟着嘴角弯起来的眼睛里读出了另一层意思——

来学快排剑法吧。来到我的领域里,用我的规则,和我比较。这样你就永远不可能超过我。

"我会考虑的。"叶辰说。

赵空明微微颔首,转身走了。

白衣在夕阳中发光,如同一段被反复优化到极致的、完美无瑕的代码。

叶辰看着他的背影消失在排序塔的拐角处。

"他建议你学快排。"NULL说。

"我知道。"

"你怎么想?"

叶辰没有立刻回答。

他站在成绩碑前,看着那两个数字——他的三层和赵空明的九层。

"冒泡排序是O(n²)。快排是O(n log n)。从纯效率的角度,快排碾压冒泡——这是常识。"叶辰缓缓开口,"但你之前说过一句话。"

"什么?"

"你说冒泡排序是我唯一的起点。然后你说了一个'而且'。"

NULL沉默了一拍。

"我说的是——'冒泡排序是你唯一的起点,而且在某些特殊场景下,它是最优解。'"

"什么特殊场景?"

NULL又沉默了。

这次的沉默更长——不是在计算,而是在斟酌措辞。

"当数据几乎已经有序时。"

叶辰眨了眨眼。

"冒泡排序在处理'几乎有序'的数据时,时间复杂度会退化为O(n)——线性复杂度。在这种场景下,它比快排还快。因为冒泡排序有一个天然的优势——它可以在一次遍历后立即判断数据是否已经有序,如果已经有序就直接停止。而快排没有这个机制——无论数据是否有序,快排都会执行完整的分治流程。"

叶辰慢慢低下头。

"反过来——快排也有它的致命弱点。"NULL继续说,声音恢复了它惯常的冷淡但精确,"当数据已经完全有序或完全逆序时,快排的时间复杂度会退化为O(n²)——和冒泡排序一样差。"

叶辰猛地抬头。

"快排也会退化?"

"会。这叫做快排的'最坏情况'。在最坏情况下,快排剑法的效率与冒泡排序掌完全相同。而制造这种'最坏情况'——刻意让输入数据变成快排最怕的排列方式——理论上是可能的。"

叶辰的心跳加速了。

"你是说——有办法破快排?"

"理论上。但这需要你在战斗中精确控制自己被攻击的'数据序列',让快排剑法的分治策略持续选到最差的基准点。这不是一般人能做到的——需要对快排的底层逻辑有极其深刻的理解,同时拥有异常精准的战场操控能力。"

NULL顿了一下。

"你不需要现在考虑这些。当务之急是——提升冒泡排序掌的完成度,并寻找适合你的进阶路径。不一定是快排——世界上不只有一种排序算法。"

叶辰缓缓吐出一口气。

他最后看了一眼成绩碑,然后转身走向碑林。

走出几步后,他停了下来。

"NULL。"

"在。"

"碑林里快排剑法的碑——你扫描过吗?"

"扫描过。快排剑法的主碑在排序术区正中央,是星级最高的石碑之一。碑文完整,代码规范,注释详尽。"

"完整?"

"……"NULL停顿了一拍,"不。不完整。我刚才说错了——碑文几乎完整。但有一段被刻意隐去了。"

叶辰的脚步停住。

"哪一段?"

"快排剑法的最后一个章节——'极端输入下的行为'。这个章节本应描述快排在最坏情况下的表现以及应对策略,但碑面上这一段被人用术式抹除了。只留下了一行备注。"

"什么备注?"

"'此段已由维护者长老移除。原因:涉及远古禁术相关内容。'"

远古禁术。

叶辰的脑海中闪过那块半人高的灰黑色石碑——"递归禁术"三个字在苔藓下若隐若现。

快排剑法的"最坏情况"——和递归禁术有什么关系?

他还不知道答案。

但他知道,这些碎片正在缓慢地、必然地拼凑在一起。

叶辰转身,走进了碑林。

夕阳将他的影子拉得很长。

在影子的尽头,源码碑林无数的石碑沉默地矗立着。它们保存着千年来无数修士的智慧——

也保存着被刻意抹去的秘密。