引
启发式分裂 (启发式分治)是 分治算法 中常用的一种基于启发式思想的优化策略。
启发式分裂大多体现在计算顺序上。本人的初步理解是:通过 合理安排分治中额外计算部分的计算顺序 以达到优化复杂度的目的。
由于关于启发式分裂的资料较少,因此本文可能存在不够严谨的地方,若有请指出。
这种东西空讲没什么感觉,就根据几道例题看看吧。
例题
Luogu P4755 Beautiful Pair
小D有个数列 \(\{a_1, a_2, \cdots a_n\}\),当一个数对 \((i,j)(i\le j)\)满足 \(a_i \times a_j \le \max\limits_{i \le k\le j} a_k\) 时,小D认为这个数对是美丽的.请你求出美丽的数对的数量。
\(1\le a_i\le 10^9, 1\le n\le 10^5\)
考虑分治算法,对于一个区间 \([l, r]\),先求出这个区间最大值的位置 \(p\),那么我们可以将这段区间分为两个主要的部分 \([l, p), (p, r]\)(位置 \(p\) 单独考虑)。
数对 \((i, j)\) 完全位于 \([l, p) \text{ or } (p, r]\) 的情况可以递归处理,现在计算 \(i\in [l, p) \And j \in (p, r]\) 的情况。
不难想到,可以对前半部分扫一遍,然后对于每一个 \(i\) 计算右边部分满足 \(a_i \times a_j \le a_p\) 的 \(j\) 的个数。转化为 \(a_j \le \dfrac{a_p}{a_i}\),发现是求 一个区间内不大于某个值的数的个数。于是可以使用主席树用一个\(\log\) 完成单次统计。
尝试着分析时间复杂度?不幸的是,如果每次递归中 \(p\) 都在非常后面的位置,那么我们会悲惨的发现复杂度被卡到了 \(O(n^2\log n)\)。于是我们尝试优化。
可以发现,上面的算法中,如果我们反过来——不扫左边而扫右边,然后用主席树完成对左边的统计,好像也不是不可以。
所以说扫哪边呢?
答案是 扫较小的区间。很显然,我们会选择用更加高效的数据结构来应付规模相对较大的问题。
接下来我们试着证复杂度:
设扫描的区间(较小的区间)的长度为 \(x\),那么 \(T(n) = T(x) + T(n-x) + O(x\log n)\)
- 最优情况下,即需要扫描的长度最小(\(x = 1\)):\(T(n) = T(n - 1) + O(\log n) = O(n\log n)\)。
- 最坏情况下,即刚好要扫描一半的当前区间(\(x = \dfrac{n}{2}\)):\(T(n) = 2T(\dfrac{n}{2}) + O(n\log n) = O(n\log^2 n)\)。
因此该算法的复杂度为 \(O(n\log^2 n)\)。于是AC。
小结
相信大家对启发式分裂有一定的了解了。
像上面的例题,我们就是用合理的计算顺序,即到底选哪边暴力,哪边用数据结构统计,优化了复杂度。
启发式分裂和启发式合并的主要思想很像,都是 “从小到大” 的原则。
实际上,这样的结论大多数是凭直觉而来,所有某些时候第一感觉于是很重要的。
中途相遇
也是一种以改变计算顺序来优化时间的手段,个人认为也属于启发式分裂的范畴。
中途相遇法的体现一般为:顺序不行,那就直接两边一起上。
为了更深入地理解这个方法,下面仍然是一个例子。
UVA 1608 CERC2012 Non-boring sequences
如果一个序列的任意连续子序列都至少有一个元素唯一,则称这个序列“不无聊”,否则称这个序列“无聊”。给定 \(T\) 个序列 \(a\),长度为 \(n(n\le 10^5)\),求是否“无聊”。
首先要知道,假如在整个数列中找到了一个位置 \(p\),\(a_p\) 的值在整个数列中是唯一的,由于子段 \(a[1, p-1]\) 和 \(a[p+1, n]\) 都满足条件,那么显然整个数列就满足条件。证明见文末链接。
根据这个性质我们可以这样分治:先找到一个满足上述条件的 \(p\),然后判断子段 \(a[1, p-1]\) 和 \(a[p+1, n]\) 是否都满足条件即可。若找不到这样的 \(p\),则数列为“无聊”的。
如何找这样的 \(p\)?如果我们直接从前往后,那么复杂度在最坏情况(\(p\) 总是在当前区间最后的位置)会被卡成 \(O(n^2)\)。
这就需要用 中途相遇 的思想了——两边同时开始向中间找。
时间复杂度?我们发现这样子的最坏情况是 \(p\) 恰好在中间:\(T(n) = 2T(\dfrac{n}{2}) + O(n) = O(n\log n)\)。假如 \(p\) 在端点周围就更快了:\(T(n) = T(n - 1) + O(1) = O(n)\)。
于是以 \(O(n\log n)\) 的优秀效率 AC 了。
小结
中途相遇法在分治中是一种常见的方法。
假如说在递归的计算中,发现正着做很慢,反着做也慢,此时不妨试试中途相遇,双管齐下。
相关题目
- Codefores 1181E2 A Story of One Country (Hard)
- LA 8257 Factor-Free Tree
- Codeforces 1156E Special Segments of Permutation
后记
- 原文地址:https://www.cnblogs.com/-Wallace-/p/13245850.html
- 本文作者:@-Wallace-
- 转载请附上出处。
Non-boring sequences 中第一个命题的证明:https://www.cnblogs.com/-Wallace-/p/12874501.html