求解算法复杂度中√𝑛被称为输入“中间”的具体含义

作者提到的“输入的中间”并非指数值上处于[1, n]区间内这么简单，核心是从算法拆分逻辑的对称性角度来说的：

• 关键在于公式√n = n/√n带来的对称特性：如果将规模为n的输入进行拆分，要么分成√n个组、每组包含√n个元素，要么分成每组√n个元素、总共得到√n组。这种拆分后两个维度的规模完全等价（渐近意义上）的性质，是logn不具备的。
• 举个实际场景：比如分块算法（如Mo's算法）就是利用了这种对称拆分——将数组分成√n块后，查询操作的块间跳转次数和块内元素处理次数都是O(√n)，两者代价平衡，最终得到介于O(logn)和O(n)之间的复杂度。
• 对比logn：logn是基于二分的层级式缩小，每一层规模是上一层的1/2，不存在这种“拆分后两部分规模对等”的平衡；而√n可以看作n和1之间的几何中点（即(1×n)^(1/2)=√n），它的增长速度刚好卡在O(logn)和O(n)之间，同时具备独特的对称拆分能力，这才是作者特意强调“输入的中间”的原因。

内容的提问来源于stack exchange，提问作者Qamber