3 分治算法

3.1

设 AAA 是 nnn 个非 000 实数构成的数组, 设计一个算法重新排列数组中的数, 使得负数都排在正数前面. 要求算法使用 O(n)O(n)O(n) 的时间和 O(1)O(1)O(1) 的空间.

算法设计：由于算法要求使用 O(n)O(n)O(n) 的时间和 O(1)O(1)O(1) 的空间，因此可以使用类似快速排序的方式将数组扫描一遍完成局部排序。而且已知AAA中只有正数和负数，因此如果以比较作为基本运算，比较的对象就是000，相当于对AAA进行一轮哨兵元素为000的快速排序。

数据输入：A[1..n]A[1 . . n]A[1..n]

结果输出：排序好的A[1..n]A[1 . . n]A[1..n]

伪码描述：

1. p←1//从起始位置向后扫描的指针p \leftarrow 1 \quad / / 从起始位置向后扫描的指针p←1//从起始位置向后扫描的指针
2. q←n//从末尾位置向前扫描的指针q \leftarrow n \quad / / 从末尾位置向前扫描的指针q←n//从末尾位置向前扫描的指针
3. whileA[p]<0andp
4. ​ p←p+1p \leftarrow p+1p←p+1
5. whileA[q]>0andp>1do//直到找到第一个负数while\ \ A[q]>0\ \ and \ \ p>1\ \ do \quad //直到找到第一个负数while  A[q]>0  and  p>1  do//直到找到第一个负数
6. ​ q←q−1q \leftarrow q-1q←q−1
7. ifp
8. thenswap(A[p],A[q]);goto3//交换两个元素并开始新一轮扫描then \ swap(A[p], A[q]);goto\ 3\quad//交换两个元素并开始新一轮扫描then swap(A[p],A[q]);goto 3//交换两个元素并开始新一轮扫描
9. elsereturnA//排序结束返回else\ return\ \ A\quad//排序结束返回else return  A//排序结束返回

复杂度分析：该算法相当于对数组进行一轮哨兵元素为000的快速排序，易得算法的时间复杂度是
W(n)=O(n)\begin{aligned} W(n)=O(n ) \end{aligned} W(n)=O(n)​
算法没有空间存储需求，全部操作都在原数组上完成，因此空间复杂度是
S(n)=O(1)\begin{aligned} S(n)=O(1 ) \end{aligned} S(n)=O(1)​

3.2

设 SSS 是 nnn 个不等的正整数集合, nnn 为偶数, 给出一个算法将 SSS 划分为子集 S1S_1S1​ 和 S2S_2S2​,使得 ∣S1∣=∣S2∣=n/2|S_1| = |S_2| = n/2∣S1​∣=∣S2​∣=n/2, 且 ∣∑x∈S1x−∑x∈S2x∣| ∑ _{x∈S_1} x − ∑ _{x∈S_2} x|∣∑x∈S1​​x−∑x∈S2​​x∣ 达到最大, 即使得两个子集元素之和的差达到最大.

算法设计：nnn个不等的正整数集合SSS的元素个数为偶数，因此n/2n/2n/2仍为整数，划分后 ∣S1∣=∣S2∣=n/2|S_1| = |S_2| = n/2∣S1​∣=∣S2​∣=n/2，要想使得∣∑x∈S1x−∑x∈S2x∣| ∑ _{x∈S_1} x − ∑ _{x∈S_2} x|∣∑x∈S1​​x−∑x∈S2​​x∣ 达到最大，就需要找出这个集合中较大或者较小的n/2n/2n/2个数，一种简易的思路就是先对集合SSS进行排序，排好序后直接按索引将前n/2n/2n/2个数划分出来作为目标子集即可达到目的。

数据输入：S[1..n]S[1 . . n]S[1..n]

结果输出：S1[1..n/2],S2[1..n/2]S_1[1..n/2], S_2[1..n/2]S1​[1..n/2],S2​[1..n/2]

伪码描述：

1. L←Sort⁡(S)//先对集合S使用排序算法进行排序得到数组LL \leftarrow \operatorname{Sort}(S) \quad / / 先对集合S使用排序算法进行排序得到数组LL←Sort(S)//先对集合S使用排序算法进行排序得到数组L
2. S1←L[1..n/2]//划分排序后的数组的到子集S1S_1 \leftarrow L[1..n/2] \quad / / 划分排序后的数组的到子集S_1S1​←L[1..n/2]//划分排序后的数组的到子集S1​
3. S2←L[n/2..n]//划分排序后的数组的到子集S2S_2 \leftarrow L[n/2..n] \quad / / 划分排序后的数组的到子集S_2S2​←L[n/2..n]//划分排序后的数组的到子集S2​
4. returnS1,S2//返回划分好的两个子集return\ \ S_1, S_2\quad//返回划分好的两个子集return  S1​,S2​//返回划分好的两个子集

复杂度分析：该算法的时间代价集中在第111行的排序算法的环节，排序的时间复杂度为 O(nlog⁡n)O(n \log n)O(nlogn)，之后的数组划分部分时间复杂度为O(1)O(1 )O(1)，因此该算法的总时间复杂度为
W(n)=O(nlog⁡n)+O(1)=O(nlog⁡n)\begin{aligned} W(n)=O(n \log n)+O(1 )=O(n \log n) \end{aligned} W(n)=O(nlogn)+O(1)=O(nlogn)​

默认排序算法都在原数组上完成，因此算法只需要常数规模的存储空间，空间复杂度是
S(n)=O(1)\begin{aligned} S(n)=O(1 ) \end{aligned} S(n)=O(1)​

3.3

设 AAA 和 BBB 都是从小到大已经排好序的 nnn 个不等的整数构成的数组, 如果把 AAA 和 BBB 合并后的数组记作 CCC, 设计一个算法找出 CCC 的中位数并给出复杂度分析.

算法设计：第一时间想到的思路是直接对AAA和BBB进行顺序遍历同时比较大小，找到第nnn个数返回，这相当于将CCC进行了排序，但是题目只需要我们给出CCC的中位数即可，显然这样的算法并不是最优解。

因此不妨采用递归分治的思想，并采用类似二分查找的方式寻找中位数，具体操作即将AAA和BBB的中位数拿出比较，如果二者相等则就是CCC的中位数，如果不相等，则根据具体情况递归查询规模减半的AAA和BBB的一半子集。

数据输入：A[1..n],B[1..n]A[1 . . n],B[1 . . n]A[1..n],B[1..n]

结果输出：CCC的中位数medianmedianmedian

伪码描述：

​ findMedian(A,B,start1,end1,start2,end2):findMedian\ (A, B, start1,end1,start2,end2):findMedian (A,B,start1,end1,start2,end2):

1. mid1←(start1+end1)/2//找到A的中间元素索引值mid1 \leftarrow (start1+end1)/2 \quad / / 找到A的中间元素索引值mid1←(start1+end1)/2//找到A的中间元素索引值
2. mid2←(start2+end2)/2//找到B的中间元素索引值mid2 \leftarrow (start2+end2)/2 \quad / / 找到B的中间元素索引值mid2←(start2+end2)/2//找到B的中间元素索引值
3. ifA[mid1]=B[mid2]//判断是否为中位数if\ \ A[mid1]=B[mid2]\quad //判断是否为中位数if  A[mid1]=B[mid2]//判断是否为中位数
4. thenreturnA[mid1]//找到峰顶返回then \ return \ A[mid1]\quad//找到峰顶返回then return A[mid1]//找到峰顶返回
5. ifA[mid1]
6. thenfindMedian(A,B,mid1,end1,start2,mid2)//递归寻找then \ findMedian\ (A, B, mid1,end1,start2,mid2)\quad//递归寻找then findMedian (A,B,mid1,end1,start2,mid2)//递归寻找
7. ifA[mid1]>B[mid2]//峰顶在前半部分if\ \ A[mid1]>B[mid2] \quad //峰顶在前半部分if  A[mid1]>B[mid2]//峰顶在前半部分
8. thenfindMedian(A,B,start1,mid1,mid2,end2)//递归寻找then \ findMedian\ (A, B, start1,mid1,mid2,end2)\quad//递归寻找then findMedian (A,B,start1,mid1,mid2,end2)//递归寻找

递推方程：
{W(n)=W(n2)+1W(1)=1\left\{\begin{array}{l} W(n)=W\left(\frac{n}{2}\right)+1 \\ W(1)=1 \end{array}\right. {W(n)=W(2n​)+1W(1)=1​
复杂度分析：该算法使用递归分治的思想，由递推方程可知，每次递归问题的规模减半，因此易得算法的时间复杂度是
W(n)=O(log⁡n)\begin{aligned} W(n)=O(\log n ) \end{aligned} W(n)=O(logn)​
算法只需要常数规模的存储空间，因此空间复杂度是
S(n)=O(1)\begin{aligned} S(n)=O(1 ) \end{aligned} S(n)=O(1)​

3.4

输入三个正整数 a,p,ka, p, ka,p,k, 求 apmodka^p\ mod\ kap mod k 的值. 提示: 由于数据的规模很大, 如果直接计算, 不仅需要采用高精度, 而且时间复杂度很大。例如 1025mod7=310^{25}\ mod\ 7 = 31025 mod 7=3, 但 102510^{25}1025 超出了整型数的表示范围，不能直接计算. 请使用分治策略实现取余运算的算法并给出复杂度分析.

算法设计：根据取余运算的相关性质：
apaqmodk=(apmodk)(aqmodk)a^pa^q\ mod \ k=(a^p\ mod\ k)(a^q\ mod\ k) apaq mod k=(ap mod k)(aq mod k)
由此想到可以对指数运算的取余操作运用分治策略，具体操作可以用以下公式概括：
apmodk=ap/2ap/2modk=(ap/2modk)(ap/2modk)a^p\ mod\ k=a^{p/2}a^{p/2}\ mod \ k=(a^{p/2}\ mod\ k)(a^{p/2}\ mod\ k) ap mod k=ap/2ap/2 mod k=(ap/2 mod k)(ap/2 mod k)
值得注意的是，在分治过程中p/2p/2p/2不一定是整数，因此需要额外考虑和处理ppp为奇数的情况。

数据输入：三个正整数 a,p,ka, p, ka,p,k

结果输出：取余运算结果resultresultresult

伪码描述：

​ Mod(a,p,k):Mod\ (a, p, k):Mod (a,p,k):

1. ifp=0//递归终止条件if\ \ p=0\quad //递归终止条件if  p=0//递归终止条件
2. thenreturn1then\ \ return\ \ 1then  return  1
3. t←Mod(a,p/2,k)//递归分治，规模减半t \leftarrow Mod\ (a, p/2, k) \quad / / 递归分治，规模减半t←Mod (a,p/2,k)//递归分治，规模减半
4. ifp%2=1//判断p是否为奇数if\ \ p\%2=1\quad //判断p是否为奇数if  p%2=1//判断p是否为奇数
5. thenreturn(t∗t∗b)%k//处理p为奇数的情况then \ return \ (t*t*b)\%k\quad//处理p为奇数的情况then return (t∗t∗b)%k//处理p为奇数的情况
6. elsereturn(t∗t)%k//p为偶数，正常返回else\ \ return \ (t*t)\%k\quad//p为偶数，正常返回else  return (t∗t)%k//p为偶数，正常返回

递推方程：
{W(n)=W(n2)+1W(1)=1\left\{\begin{array}{l} W(n)=W\left(\frac{n}{2}\right)+1 \\ W(1)=1 \end{array}\right. {W(n)=W(2n​)+1W(1)=1​
复杂度分析：该算法使用递归分治的思想，每次递归问题的规模减半，因此易得算法的时间复杂度是
W(n)=O(log⁡n)\begin{aligned} W(n)=O(\log n ) \end{aligned} W(n)=O(logn)​
算法只需要常数规模的存储空间，因此空间复杂度是
S(n)=O(1)\begin{aligned} S(n)=O(1 ) \end{aligned} S(n)=O(1)​