重修初赛

喵仔牛奶 · 2026-06-30 11:35:55 · 算法·理论

声明：没什么意义的文章，给大家看个乐子 /kel

今天上午啥也不想学，和 Gold14526 闲聊的时候发现怎么五维、六维、甚至任意维数点都可以做到单根号，于是发现自己对复杂度的理解有一些错误，写了这篇文章。

大家都知道，k 维数点可以通过 CDQ 分治做到 \mathcal O(n\log^{k-1}n) 的复杂度。具体来说就是 T_k(n)=2T_k(n/2)+T_{k-1}(n)，T_2(n)=\mathcal O(n\log n)，根据主定理得到 T_k(n)=\mathcal O(n\log^{k-1}n)。这个时候你灵机一动，二维数点可以做到 T_2(n)=\mathcal O(n\sqrt n)，那我再用主定理算不就变成 T_k(n)=\mathcal O(n\sqrt n) 了？这样是一个优化吗？

考虑一下 10 维数点的情况，前者复杂度 \mathcal O(n\log^{9}n)，后者复杂度 \mathcal O(n\sqrt n)——在 OI 范围内肯定是后者优吧！

好吧，这样确实太不严谨了，而且渐进意义下还是前者更优。我们给出一个后者可能比前者优的“证明”：对于一个固定的 n，考虑 k 增大的过程，前者每次乘以 \mathcal O(\log n)，而后者每次乘一个常数 c。因此总是可以找到一个 n 使得 \mathcal O(\log n) 比 c 大，此时 k\to\infty 就后者更优了！

——但是你又感觉不对了！设时间复杂度为 T_{1,k}(n),T_{2,k}(n)，由于 \forall n\in\mathbb N^+,\frac{1}{2}n\log n<n\sqrt n，设两个这算法常数因子为 c_1,c_2，就有 \forall n\in\mathbb N^+,\frac{1}{2c_1}T_{1,1}(n)<\frac{1}{c_2}T_{2,1}(n)，那归纳一下就得到对于所有 k 都有 \forall n\in\mathbb N^+,\frac{1}{2c_1}T_{1,k}(n)<\frac{1}{c_2}T_{2,k}(n)。2c_1,c_2 都是小常数，忽略不记，于是前者总是优于后者。诶，怎么和前面矛盾了？

问题究竟出在哪？答案是我们不能既在过程中忽略常数又在最后将 k 当作变量分析。

我们来重新分析一下。将复杂度简化为这样两个递归式：

对于前者，令 f_k(m)=2^{-m}F_k(2^m)，则 f_k(m)=f_k(m-1)+f_{k-1}(m)，f_1(m)=m，得到 f_k(m)=\binom{m+k-1}{k}，由此 F_k(n)=\Theta\big(n\cdot\binom{\log_2n+k-1}{k}\big)。

对于后者，同样令 g_k(m)=2^{-m}G_k(2^m)，则 g_k(m)=g_k(m-1)+g_{k-1}(m)，g_1(m)=2^{m/2}，归纳可得 g_k(m)=\Theta((2+\sqrt 2)^{k}2^{m/2})。因此 G_k(n)=\Theta((2+\sqrt 2)^k\cdot n\sqrt n)。

此时我们再来看前面的两个问题。

关于比较 \mathcal O(n\log^{9}n) 与 \mathcal O(n\sqrt n)，根据 F_k(n) 和 G_k(n) 来计算。认为 k 是小常数，那么 \binom{\log_2n+k-1}{k}\approx\frac{1}{k!}\log_2^kn，前者有一个 9!^{-1}\approx 2.75\times10^{-6} 的常数；后者有一个 (2+\sqrt 2)^9\approx 6.30\times10^4 的常数。此时再代入 n 计算，就可以正确得到前者小于后者的结果。

关于固定 n 对 k\to\infty 的分析，n 看作常数，则有 F_k(n)=\Theta\big(n\cdot\binom{\log_2n+k-1}{k}\big)=\Theta(k^{\log_2n-1})，G_k(n)=\Theta((2+\sqrt 2)^k\cdot n\sqrt n)=\Theta((2+\sqrt 2)^k)。前者是多项式级而后者是指数级，可以正确得到 k\to\infty 时 F_k(n)<G_k(n) 的结果。