2023.8集训

发表于 2023-08-26 更新于 2023-08-27 本文字数： 936 阅读时长 ≈ 1 分钟

记一些集训过程中奇怪的想法

\(2023.8.14-2023.8.25\)

记一些集训过程中奇怪的想法

很多算法可以实现不同复杂度的不同操作。对于同一操作集合也有很多不同的算法来实现。比如，在规模为\(n\)的\(RMQ\)问题就有如下实现方式：

算法	预处理	单点修改	区间查询	空间复杂度
遍历	\(\Theta(n)\)	\(\Theta(1)\)	\({\rm O}(n)\)	\(\Theta(n)\)
\(ST\)表	\(\Theta(n)\)	\({\rm O}(n)\)	\(\Theta(1)\)	\(\Theta(n\log n)\)
线段树	\(\Theta(n)\)	\(\Theta(\log n)\)	\({\rm O}(\log n)\)	\(\Theta(n)\)
树状数组	\(\Theta(n\log n)\)	\({\rm O}(\log n)\)	\({\rm O}(\log n)\)	\(\Theta(n)\)
\(Four Russian\)	\(\Theta(n\log\log n)\)	\(\Theta(\frac{n}{\log n})\)	\(\Theta(1)\)	\(\Theta(n\log\log n)\)

对于同一操作集合，列举实现它所有算法的\(\{预处理,单点修改,区间查询,空间复杂度\cdots \}\)向量

这个向量还可能包含更多元素，如均摊复杂度、最坏复杂度，还有排序算法中是否稳定等等……这个向量可以更长，甚至无限长

猜想这些向量在向量空间中分布与某超平面的一侧（包含这个超平面），其中位于超平面上的算法是在某些情况下复杂度最优的

毕竟我们可以通过while(1)强行增加复杂度，所以这些向量组成的集合应是一个与向量空间同维度的“体”，而不是比向量空间维度更低的“面”或“线”。处于这个“体”的边界（也就是上文中的超平面）上的向量就是没有“复杂度损失”的算法

而不同实现操作集合的算法，其对应的超平面是否存在某种规律，是的我们经常观察到某些“优化”可以使某两个操作的复杂度从\(({\rm O}(n),{\rm O}(1))\)“优化”至\(({\rm O}(\log n),{\rm O}(\log n))\)？