chap 2-3 分治算法-综合应用

    Blog  0 visits

1. 满二叉树的数量

定义满二叉树：所有节点要么有两个子节点，要么无子节点。设$B_n$表示共$n$节点的不同满二叉树的数量，则：

$$
B_{n+2}=\sum_{i=1}^{n+1}B_{i}B_{n+1-i}
$$

假设根节点固定，则$n+2$个节点的满二叉树数量，取决于根节点的左子树和右子树（都为满二叉树）的组合数量。使用数学归纳法可证，复杂度为$\Omega(2^n)$。我们可以使用额外的空间保存下$B_i$的值，这样可以减少重复计算次数。

2. 二分查找模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int binary_search(int* nums, int n, int target) {
    int left = 0, right = n - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            return mid;
        }
    }
    return -1;
}

int lower_bound(int* nums, int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            right = mid - 1;
        }
    }
    if (left >= n || nums[left] != target)
        return -1;
    return left;
}

int upper_bound(int* nums, int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            left = mid + 1;
        }
    }
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

3. 无限数列中的搜索

给定无限数列$A[\cdot]$，前$n$个元素都是有序的整数，后面的无限个元素都是$\infty$，且$n$是未知的。设计一个复杂度为$O(\log n)$的查找算法。

依次访问以下元素：$A[0], A[1],A[2],A[4],A[8],\cdots,A[2^{k-1}],A[2^k]$，直至$A[2^k]=\infty$，则$2^{k-1}\leq n-1 < 2^k$。在$A[2^{k-1},\cdots,2^k]$范围内做二分搜索，可以在$O(\log n)$内找到$n$。得知$n$后，就可以使用二分搜索在$O(\log n)$内查找任意元素。

4. 搜索复杂度下界

类比排序算法，基于比较的搜索算法也可以用决策树模型来描述。二叉树至少有$n$个叶子节点，每个叶子节点代表查找到的索引值，每个非叶子节点代表一次比较操作，二叉树的高度代表搜索次数，故复杂度为$\Omega(\log n)$。

5. k-way merge

给定$k$个有序数组，每个数组都是$n$个元素，设计算法将其合并成一个具有$kn$个元素的有序数组。

第一种做法：为了选出最小的元素，比较所有数组的第一个元素（$k-1$次）。每次比较的时间为$O(k)$，共需选出$O(kn)$个元素，总复杂度为$(k^2n)$。

第二种做法：顺序合并，第一个数组先和第二个数组合并，将合并的结果与第三个数组合并…… 令$T(i)$表示合并数组$1~i$的时间，则$T(i)\leq T(i-1)+O(ni)$，总复杂度为$O(k^2n)$。

第三种做法：使用分治法，两两合并，将合并的结果再两两合并…… 递归表达式：$T(k)=2T(k/2)+O(nk)$，复杂度为$O(nk\log k)$。

第四种做法：使用堆实现的优先队列。先把$k$个有序数组的第一个元素输入优先队列中，复杂度为$O(k\log k)$。接下来，可以在$O(\log k)$时间内，完成优先队列的push、pop操作，共需进行$kn$次，故总复杂度为$O(nk\log k)$。

第五种做法：使用败者树（类似于堆），步骤类似于第四种做法，总复杂度为$O(nk\log k)$。虽然渐进意义上复杂度和优先队列相同，但是这种做法相较于优先队列，总的比较次数要略小。

6. 线性时间排序

如果排序算法基于元素比较，那么复杂度的下界为$\Omega(n\log n)$。下面介绍几种不基于比较的算法，复杂度可以轻松突破$\Omega(n\log n)$的下界。

6.1 计数排序（counting sort）

假设数组$a$有$n$个元素，每个元素都是在$[0:k]$区间内的一个整数。计数排序的基本思想就是：对于每个输入元素$a[i]$，计算出原数组中小于等于它的元素个数，就可以直接把它放在结果数组的正确位置上了。主要步骤：

  1. 建立数组$c[0:k]$，全部初始化为0。遍历数组$a$，每次遇到$a[i]$，就在$c[a[i]]$上加1。遍历完后，$c[i]$存储的就是$i$在数组$a$中出现的次数。
  2. 从前往后遍历$c[i]$，对于每个$c[i]$，令$c[i]=c[i]+c[i-1]$，此时$c[i]$表示数组$a$中$\leq i$的元素个数，且$c[k]=n$。
  3. 建立数组$b$存储结果，从后往前遍历数组$a$，对于$a[i]$，应该有$c[a[i]]$个元素小于等于它，所以它在最终结果中的下标应该是$c[a[i]]-1$，故$b[c[a[i]]-1]=a[i]$。由于$a[i]$已经被填入结果数组中，所以$c[a[i]]$的值应该减1。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
void counting_sort(int* a, int n, int k) {
	int* b = new int[n];
	int* c = new int[k+1];
	for (int i = 0; i <= k; ++i) c[i] = 0;
	for (int i = 0; i < n; ++i) c[a[i]]++;
	for (int i = 1; i <= k; ++i) c[i] += c[i-1];
	for (int i = n-1; i >= 0; --i) {
		b[c[a[i]]-1] = a[i];
		c[a[i]]--;
	}
	for (int i = 0; i < n; ++i) a[i] = b[i];
	delete[] b; delete[] c;
}

容易看出，复杂度为$\Theta(n+k)$。若$k=O(n)$，则复杂度为$\Theta(n)$。

注意到在步骤3中，我们从后往前遍历数组$a$，是为了保证排序的稳定性：具有相同值的元素在输出数组中的相对次序和在输入数组中的相对次序相同。若我们从前往后遍历数组$a$，相同的元素在输出数组中相对于之前就是逆序的。

为什么需要保证排序稳定性？如果元素只表示数字的话，可以不用考虑。但是在实际应用中，需要排序的元素可能是一个个复杂对象，实际参与排序的元素只是一个句柄（handle），可能是对象指针或一个整数，一个句柄关联一个对象。如果这些对象本来具有某种顺序，排序不稳定的话就会破坏这种顺序。

6.2 基数排序（radix sort）

给定一个数组，数组元素都是日期时间格式（yyyy-MM-dd HH:mm:ss），需要按照时间先后顺序对其进行排序。第一种方法是，先按照年排序，年相同的再按照月排序，月相同的…… 另一种方法便是基数排序，使用一种稳定排序算法对这些信息进行6次排序，先秒，再分，后小时…… 这种多关键字域的排序可以考虑使用基数排序。

对于一般的整数排序，也可以使用基数排序。给定$n$个$d$位整数（第一位为最低位，第$d$位为最高位），我们可以先使用稳定排序对第1位排序，然后对第2位排序，直至第$d$位。举例，下面有一组数：

$$
329,457,657,839,436,720,355
$$

我们先对最低位排序（9，7，7，9，6，0，5）：

$$
720,355,436,457,657,329,839
$$

然后对第2位排序（2，5，3，5，5，2，3）：

$$
720,329,436,839,355,457,657
$$

最后对最高位排序（7，3，4，8，3，4，6）：

$$
329,355,436,457,657,720,839
$$

基数排序的伪代码如下，$A$为$n$个$d$位元素：

1
2
3
function radix_sort(A, d):
	for i = 1 to d:
		stable_sort(A) on digit i

基数排序先按最低有效位进行排序确实有点反直觉，不过只要保证中间排序是稳定的，就可以得到正确结果。

$Proof$：使用数学归纳法，假设按数组元素的最低$i-1$个有效位排序后数组是有序的，下面按第$i$位进行排序。若两个元素的第$i$位不同，排序的结果一定是正确的，不用考虑最低$i-1$个有效位是否排序过以及排序是否稳定。若两个元素的第$i$位相同，排序结果取决于最低$i-1$个有效位的排序结果。由于排序是稳定的，第$i$位相同时，元素的相对次序不会改变，而且我们假设数组元素的最低$i-1$个有效位排序后数组是有序的，故按第$i$位进行排序后排序结果也正确。▮

对$n$个$b$位整数排序时，我们也可以把一个$b$位数分成$d=\lceil b/r \rceil$个$r$位数，每个$r$位数都在区间$[0,2^r-1]$中，可以采用计数排序（稳定，$k=2^r-1$）作为中间排序。每一轮排序时间为$\Theta(n+2^r)$，需要$d$轮，总时间为$\Theta((b/r)(n+2^r))$。若$b=O(\log n)$，我们选择$r=O(\log n)$，基数排序的运行时间就为$\Theta(n)$。

虽然以计数排序作为中间稳定排序的基数排序运行时间是线性，我们大多数时候仍采用快速排序。因为快速排序是原址的，只需要固定的额外空间，而基数排序要占用大量空间，且输入数据的个数满足一定条件才能达到线性时间。

6.3 桶排序（bucket sort）

假设输入数据符合均匀分布，我们可以使用桶排序。输入数组$A$的$n$个元素由随机过程产生，独立地分布在区间$[0,1)$上。主要步骤：

  1. 将区间$[0,1)$划分为$n$个相同大小的区间，称为桶。桶数组记为$B$，每个元素是一个链表结构。
  2. 依次将$A[i]$放入到对应的桶中，对应桶的下标为$\lfloor nA[i]\rfloor$。由于输入均匀分布，每个桶中的元素应该差不多。
  3. 对每个桶中的元素进行插入排序。
  4. 遍历每个桶，依次取出桶中的元素，合成一个数组。

复杂度不太容易能看出来，步骤1，2，4的复杂度都是$O(n)$，下面重点求解步骤3的平均复杂度。

假设$n_i$表示桶$B[i]$中元素的个数，步骤3的时间为：

$$
T(n)=\Theta(n)+\sum_{i=0}^{n-1}O(n_i^2)
$$

$$
E[T(n)]=\Theta(n)+\sum_{i=0}^{n-1}O(E[n_i^2])
$$

定义指示变量$X_{ij}=I(A[j]落入桶i)$，则：

$$
n_i=\sum_{j=1}^nX_{ij}
$$

下面求解$E[n_i^2]$：

$$
\begin{equation}
\begin{aligned}
E[n_i^2]
& = E[\sum_{j=1}^n\sum_{k=1}^nX_{ij}X_{ik}] \\ &= E[\sum_{j=1}^nX_{ij}^2+\sum_{1\leq j\leq n}\sum_{1\leq k\leq n,k\neq j}X_{ij}X_{ik}] \\ &= \sum_{j=1}^nE[X_{ij}^2]+\sum_{1\leq j\leq n}\sum_{1\leq k\leq n,k\neq j}E[X_{ij}X_{ik}] \\ &= \sum_{j=1}^nE[X_{ij}^2]+\sum_{1\leq j\leq n}\sum_{1\leq k\leq n,k\neq j}E[X_{ij}]E[X_{ik}] \\ &= [1^2\cdot \frac{1}{n}+0^2\cdot(1-\frac{1}{n})]+n(n-1)\cdot\frac{1}{n}\cdot\frac{1}{n} \\ &= 2-\frac{1}{n}
\end{aligned}
\end{equation}
$$

故总复杂度：

$$
\Theta(n)+n\cdot O(2-\frac{1}{n})=\Theta(n)
$$

我们基于的假设是输入数据符合均匀分布。观察上述推导过程，其实只要$\sum_{i=0}^{n-1}O(n_i^2)$为线性就可以，即所有桶的大小的平方和与总元素数呈线性关系。

7. 中位数和平均数

统计学中的一个重要任务就是使用单独的一个量$\mu$来描述一组观测值$x_1,x_2,\cdots,x_n$。最常用的两种统计量就是中位数$\mu_1$和平均数$\mu_2$。

中位数$\mu_1$的性质：

$$
\mu_1=\arg\min_{\mu}\sum_{i=1}^{n}|x_i-\mu|
$$

$Proof$：假设$\mu>\mu_1$，令$\mu$往$\mu_1$的方向移动一个极小的偏移量$\epsilon$，则所有$x_i<\mu$的$x_i$到$\mu$的距离都减少了$\epsilon$，所有$x_i>\mu$的$x_i$到$\mu$的距离都增大了$\epsilon$。由于$\mu>\mu_1$，比$\mu$小的$x_i$的数量一定不小于比$\mu$大的$x_i$的数量，故总距离应该是单调递减的。同理，假设$\mu<\mu_1$，则令$\mu$往$\mu_1$的方向移动时，总距离也是单调递减的。故上述性质成立。▮

平均数的性质：

$$
\mu_2=\arg\min_{\mu}\sum_{i=1}^{n}(x_i-\mu)^2
$$

$Proof$：通过推导，可以得出：

$$
\sum_{i=1}^{n}(x_i-\mu)^2=\sum_{i=1}^{n}(x_i-\mu_2)^2+n(\mu-\mu_2)^2
$$

当$\mu=\mu_2$时，上式取最小值，故结论成立。▮

从这个性质也可以看出，平均数非常容易受观测序列中离群值（outlier）的影响。

8. 两个有序数组的 k th smallest element

给定两个升序数组$a$和$b$，长度分别为$m$和$n$，设计算法求出两个数组的并集的第$k$小的元素，复杂度为$O(\log k)$。

首先缩小搜索范围，两个数组的并集的第$k$小的元素一定在$a[0:k-1]$和$b[0:k-1]$之中（若$m<k$或$n<k$，就把不足$k$的部分设置成$\infty$）。需要求解的问题：在$a[0:k-1]$和$b[0:k-1]$的并集中寻找第$k$小的元素。

令$k_f=\lfloor k/2 \rfloor, k_c=\lceil k/2 \rceil$（$k_f+k_c=k$），比较$a[k_f-1]$和$b[k_c-1]$的大小。

  1. 若$a[k_f-1]>b[k_c-1]$，说明了$a[k_f-1]>b[0:k_c-1]$共$k_c$个元素，可以推出比$b[k_c-1]$还要小的元素最多只可能有$k-2$个：$b[0:k_c-2]$和$a[0:k_f-2]$。因此，第$k$小的元素一定$>b[k_c-1]$。由于$a[k_f-1]$是$a[0:k_f-1]$和$b[0:k_c-1]$中最大的，且这两个区间共有$k$个元素，故第$k$小的元素一定$\leq a[k_f-1]$。

    综上所述，原问题被缩减成了子问题：在$a[0:k_f-1]$和$b[k_c:n-1]$的并集中寻找第$k-k_c=k_f$小的元素。

  2. 若$a[k_f-1]<b[k_c-1]$，说明了$a[k_f-1]<b[0:k_c-1]$共$k_c$个元素，可以推出比$a[k_f-1]$还要小的元素最多只可能有$k-2$个：$b[0:k_c-2]$和$a[0:k_f-2]$。因此，第$k$小的元素一定$>a[k_f-1]$。由于$b[k_c-1]$是$a[0:k_f-1]$和$b[0:k_c-1]$中最大的，且这两个区间共有$k$个元素，故第$k$小的元素一定$\leq b[k_c-1]$。

    综上所述，原问题被缩减成了子问题：在$a[k_f:m-1]$和$b[0:k_c-1]$的并集中寻找第$k-k_f=k_c$小的元素。

  3. 若$a[k_f-1]=b[k_c-1]$，由于$k_f+k_c=k$，且$a[k_f-1]$和$b[k_c-1]$是$a[0:k_f-1]$和$b[0:k_c-1]$中最大的，所以第$k$小的元素就是$a[k_f-1]$或$b[k_c-1]$。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
int select_from_two_sorted_array(int* a, int la, int ra, int* b, int lb, int rb, int k) {
	int na = ra - la;
	int nb = rb - lb;
	if (k == 1) return min(na > 0 ? a[la] : INT_MAX, nb > 0 ? b[lb] : INT_MAX);
	int kf = k / 2;
	int kc = k % 2 == 0 ? k / 2 : (k + 1) / 2;
	int am = la + kf - 1 < ra ? a[la + kf - 1] : INT_MAX;
	int bm = lb + kc - 1 < rb ? b[lb + kc - 1] : INT_MAX;
	if (am == bm) return am;
	else if (am > bm) return select_from_two_sorted_array(a, la, min(la + kf, ra), b, min(lb + kc, rb), rb, kf);
	else return select_from_two_sorted_array(a, min(la + kf, ra), ra, b, lb, min(lb + kc, rb), kc);
}

复杂度分析：每次递归$k$都变为原来的一半，故复杂度为$O(\log k)$，与数组长度无关。

9. 数组的主元

数组$A$中有$n$个元素，每个元素都是复杂类型，无法比较大小，但是能够判断两个元素是否相同。若$A$中超过一半的元素都相同，我们称这个元素为主元。设计一个算法，判断给定数组中是否存在主元，若有，则找出主元。

第一种思路，采用分治法，把$A$平均分成$A_1$和$A_2$，递归寻找出$A_1$和$A_2$的主元$v_1$和$v_2$。若$A$存在主元，则主元一定是$v_1$和$v_2$，再加以验证一下即可。具体实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
bool major_element(int* a, int l, int r, int* major) {
	if (r - l == 0) return false;
	if (r - l == 1) {
		*major = a[l];
		return true;
	}
	int m = l + (r - l) / 2;
	int* major1 = new int; 
	int* major2 = new int; 
	if (major_element(a, l, m, major1)) {
		int cnt = 0;
		for (int i = l; i < r; ++i) {
			if (a[i] == *major1) cnt++;
		}
		if (cnt >= m + 1) {
			*major = *major1; 
			delete major1; delete major2; 
			return true;
		}
	}
	if (major_element(a, m, r, major2)) {
		int cnt = 0;
		for (int i = l; i < r; ++i) {
			if (a[i] == *major2) cnt++;
		}
		if (cnt >= m + 1) {
			*major = *major2; 
			delete major1; delete major2; 
			return true;
		}
	}
	return false;
}

列出如下的递归表达式：

$$
T(n)=2T(n/2)+O(n)
$$

复杂度为$O(n\log n)$。

第二种思路：

  1. 若$n$为偶数，则把数组中的元素两两配对，两个元素相同，就丢弃任意一个；两个元素不同，就全部丢弃。
  2. 若$n$为奇数，则取出一个元素验证其是否是主元，若不是，剩余部分当作$n$为偶数的情况处理。每一轮，数组的元素个数至少变为前一轮的一半，最终剩下的元素将为主元。

$Proof$：

若$n$为偶数，假设$v$为配对删除操作后剩余$n/2$元素数组的主元，则$v$出现的次数$\geq\lfloor n/4\rfloor+1$，根据配对法则，$v$在$n$元素数组中出现的次数$\geq 2\lfloor n/4\rfloor+2 > 2(n/4-1)+2=n/2$，说明$v$也是原数组的主元。

若$n$为奇数，假设$v$为配对删除操作后剩余$n-1$素数组的主元，则$v$出现的次数$\geq(n-1)/2+1=n/2+1/2>n/2$，说明$v$也是原数组的主元。▮

具体实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
bool major_element2(int* a, int n, int* major) {
	if (n == 0) return false;
	if (n == 1) {
		*major = a[0];
		return true;
	}
	if (n % 2 == 0) {
		int* aa = new int[n / 2];
		int k = 0;
		for (int i = 0; i < n; i += 2) {
			if (a[i] == a[i + 1]) aa[k++] = a[i];
		}
		bool res = major_element2(aa, k, major);
		delete[] aa;
		return res;
	} else {
		int cnt = 0;
		for (int i = 0; i < n; ++i) {
			if (a[i] == a[n-1]) cnt++;
		}
		if (cnt >= n / 2 + 1) {
			*major = a[n-1];
			return true;
		}
		else return major_element2(a, n - 1, major);
	}
}

递归表达式：

$$
\begin{equation}
\begin{aligned}
T(n)=
& = \frac{1}{2}[T(n/2)+O(n)]+\frac{1}{2}[T(n-1)+O(n)] \\ &= \frac{1}{2}[T(n/2)+O(n)]+\frac{1}{2}[T(n/2)+O(n)] \\ &= T(n/2)+O(n)
\end{aligned}
\end{equation}
$$

复杂度为$O(n)$。

10. Modular Fourier Transform

普通的傅里叶变换涉及复数的运算，较为繁琐，而且如果多项式的系数非常大，也不便运算，故我们寻找一种模运算体系下的傅里叶变换。假设$n=6$，原来$\omega_6=e^{2\pi i/6}$，现在令$\omega_6=3$，可以发现：

$$
1+\omega_6^1+\omega_6^2+\omega_6^3+\omega_6^4+\omega_6^5\equiv 0 (\mod 7)
$$

上述性质与$n$个复数根满足的性质相同。下面我们类比普通的FT，构造模运算下的系数矩阵：

$$
M_6(\omega)
\equiv
\begin{equation}
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 3 & 2 & 6 & 4 & 5 \\ 1 & 2 & 4 & 1 & 2 & 4 \\ 1 & 6 & 1 & 1 & 6 & 1 \\ 1 & 4 & 2 & 1 & 4 & 2 \\ 1 & 5 & 4 & 6 & 2 & 3
\end{bmatrix}
\end{equation}
(\mod 7)
$$

$\frac{1}{6}\mod 7$的逆元为6，对原矩阵中每个元素也求逆元，则该矩阵的逆矩阵为：

$$
M_6(\omega)^{-1}
\equiv
\frac{1}{6}M_6(\omega^{-1})
\equiv
6\cdot
\begin{equation}
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 5 & 4 & 6 & 2 & 3\\ 1 & 4 & 2 & 1 & 4 & 2 \\ 1 & 6 & 1 & 1 & 6 & 1 \\ 1 & 2 & 4 & 1 & 2 & 4 \\ 1 & 3 & 2 & 6 & 4 & 5
\end{bmatrix}
\end{equation}
(\mod 7)
$$

现在使用上述的FT modulo 7对多项式$A(x)=x^2+x+1$和$B(x)=x^3+2x-1$做乘法，向量$\mathbb{a}\equiv(1,1,1,0,0,0) (\mod 7)$，向量$\mathbb{b}\equiv(-1,2,0,1,0,0)\equiv(6,2,0,1,0,0) (\mod 7)$。对两个向量做傅里叶变换，$M_6(\omega)\mathbb{a}\equiv (3,6,0,1,0,3) (\mod 7)$，$M_6(\omega)\mathbb{b}\equiv (2,4,4,3,1,1) (\mod 7)$，然后做点乘得到$\mathbb{c}\equiv (6,3,0,3,0,3)(\mod 7)$，最后做逆变换得到相乘结果：$M_6(\omega)^{-1}\mathbb{c}\equiv (-1,1,1,3,1,1) (\mod 7)$。

由此看来，并不是一定要以复数根作为傅里叶变换的基底，只要满足一定的条件，实数也可以作为基底。

11. Revisit gcd

之前使用欧几里得算法：$gcd(a,b)=gcd(b,a\mod b)$来计算最大公因数，现在使用分治法，假设$a\geq b$：

$$
\begin{equation}
gcd(a,b)=
\begin{cases}
2gcd(a/2,b/2), & a,b都是偶数 \\ gcd(a/2,b), & a为偶数,b为奇数 \\ gcd((a-b)/2,b), & a,b都是奇数
\end{cases}
\end{equation}
$$

$Proof$：

若$a,b$都是偶数，设$gcd(a,b)=d,a=da’,b=db’$，则$gcd(a’,b’)=1$。由于$a,b$都是偶数，说明$2$整除$d$，故$a=(d/2)a’,b=(d/2)b’$，则$gcd(a/2,b/2)=d/2$。

若$a$为偶数，$b$为奇数，则$gcd(a,b)=d$一定是奇数，$d$整除$a$的话，$d$也一定能整除$a/2$。（$d$没有因子2）

若$a,b$都是奇数，使用结论：$gcd(a,b)=gcd(a-b,b)$，再使用情况2的结论。▮

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
int gcd_divide_conquer(int a, int b) {
	if (a == 0) return b;
	if (b == 0) return a;
	if (a % 2 == 0) {
		if (b % 2 == 0) return 2 * gcd_divide_conquer(a / 2, b / 2);
		else return gcd_divide_conquer(a / 2, b);
	}
	else {
		if (b % 2 == 0) return gcd_divide_conquer(a, b / 2);
		else return a >= b ? gcd_divide_conquer((a - b) / 2, b) : gcd_divide_conquer((b - a) / 2, a);
	}
}

算法复杂度分析：假设$a,b$都是$n-bit$，算法每次至少将$a,b$中的一个减为一半，所有最多递归$O(n)$次，每次的移位、减法操作复杂度为$O(n)$，故总复杂度为$O(n^2)$。这比欧几里得算法$O(n^3)$要快。

12. 最近的点对

平面中有$n$个点：{ $p_1=(x_1,y_1),p_2=(x_2,y_2),\cdots,p_n=(x_n,y_n)$ }，如何在$O(n\log n)$内找出距离最近的点对？

首先找到所有点的横坐标的中位数$x$，以中位数$x$为界限，把点分成左右两组：$L$和$R$。

然后递归地在$L$和$R$中寻找最近的点对：$(p_L,q_L)\in L,(p_R,q_R)\in R$，最近的距离分别为$d_L$和$d_R$，令$d=\min(d_L,d_R)$。

最近的点对有可能是一个点在$L$中，另一个在$R$中，所以下面要求出这种情况下最近的点对。把$x_i\in[x-d,x+d]$的点单独分为一组：$M$，则易知这种情况下最近的点对一定在$M$中。我们可以遍历$M$中所有的点对（$O(n^2)$），计算出两两之间的距离，得出最近点对，但是其实不需要遍历全部的点对，下面是证明。

假设现在有一个$d\times d$的区域，那么里面最多包含$L$中的四个点。$Proof$：若该区域包含5个$L$中的点，把该区域分成四个$d/2\times d/2$的小区域，其中一个小区域一定包含2个$L$中的点，它们之间的距离最大为$d/\sqrt{2}<d$，与最近的点对距离为$d$矛盾，故结论成立。▮ 同理，一个$d\times d$的区域里面最多包含$R$中的四个点。

下面对$M$中的点按纵坐标的值排序，按纵坐标值从小到大遍历$M$中的一个点$(x_i,y_i)$，若$M$中存在另一个点使得它们两点间的距离小于$d$，那个点一定在$(x-d,y_i),(x-d,y_i+d),(x+d,y_i),(x+d,y_i+d)$组成的长方形区域中。该区域与$L$的交集最大为$d\times d$，与$R$的交集最大也为$d\times d$。根据上述推论，长方形区域中最多有8个点。

因此，对$M$中的点按纵坐标的值排序后（$O(n\log n)$），我们只需要遍历$M$中所有的点，计算出每个点与其后面的连续7个点间的距离（$O(1)$），得出最近点对即可。

列出递归表达式：

$$
T(n)=2T(n/2)+O(n\log n)
$$

复杂度为$O(n\log^2 n)$。优化一下，我们在一开始就对所有点按纵坐标排序，而不是每次递归中排序：

$$
T(n)=2T(n/2)+O(n)
$$

复杂度为$O(n\log n)$，一开始就排序的复杂度恰好也是$O(n\log n)$，故总复杂度为$O(n\log n)$。

13. 分位数（Quantiles）

一组数据的$k$分位数是指，将数据排序后，能把数据分成数量接近的$k$个组的$k-1$个分割点。比如，数组$A$的二分位数就是中位数。设计一个算法求出数组$A$的所有$k$分位数。

第一种思路，使用快速选择算法$k-1$次，第$j$次选出第$jn/k$小的元素，复杂度为$O(nk)$。

第二种思路，使用分治法。

  1. 若$k$为偶数，使用in-place快速选择算法找出中位数，此时中位数不小于它前面的元素，不大于它后面的元素。然后以中位数为界，递归地找出左边数列（前$(n+1)/2$个元素）的$k/2$分位数和右边数列（剩余元素）的$k/2$分位数，最后合并左边的$k/2-1$个$k/2$分位数，中位数，右边的$k/2-1$个$k/2$分位数。
  2. 若$k$为奇数，使用in-place快速选择算法找出第$n/k$大的数，然后递归地找出它后面元素的$k-2$个$k-1$分位数，最后合并第$n/k$大的数和$k-2$个$k-1$分位数。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int median(int* a, int l, int r) {
	return quickselect(a, l, r, ((r - l) + 1) / 2);
}

// k > 1
int* quantile(int* a, int l, int r, int k) {
	int n = r - l;
	if (k == 2) {
		int* res = new int[1];
		res[0] = median(a, l, r);
		return res;
	}
	if (k % 2 == 0) {
		int m = median(a, l, r);
		int* left = quantile(a, l, l + (n + 1) / 2, k / 2);
		int* right = quantile(a, l + (n + 1) / 2, r, k / 2);
		int* res = new int[k - 1];
		int i = 0;
		for (; i < k / 2 - 1; ++i) res[i] = left[i];
		res[i++] = m;
		for (; i < k - 1; ++i) res[i] = right[i-k/2];
		return res;
	} else {
		int q = quickselect(a, l, r, n / k);
		int* right = quantile(a, l + n / k, r, k - 1);
		int* res = new int[k - 1];
		res[0] = q;
		for (int i = 1; i < k - 1; ++i) res[i] = right[i - 1];
		return res;
	}
}

递归表达式：

$$
\begin{equation}
\begin{aligned}
T(k)
& = \frac{1}{2}[T(k/2)+O(n)]+\frac{1}{2}[T(k-1)+O(n)] \\ &= \frac{1}{2}[T(k/2)+O(n)]+\frac{1}{2}[T(k/2)+O(n)] \\ &= T(k/2)+O(n)
\end{aligned}
\end{equation}
$$

复杂度为$O(n\log k)$。

14. Revisit FFT (base=3)

在进行FFT时，若向量$\mathbb{a}$的长度不是2的幂，而是3的幂，我们也可以使用基为3的快速傅里叶变换。

假设$A(x)=a_0+a_1x+a_2x^2+\cdots,a_8x^8$，令$\omega_9$为主8次复数根，把多项式系数下标按照$\mod 3$余数的不同，分成三组$A(x)=A_0(x^3)+xA_1(x^3)+x^2A_2(x^3)$，则：

$$
\begin{equation}
\begin{aligned}
A(w_9^k)
&= A_0(w_3^{k})+w_9^kA_1(w_3^{k})+w_9^{2k}A_2(w_3^{k})
\end{aligned}
\end{equation}
$$

$$
\begin{equation}
\begin{aligned}
A(w_9^{k+3})
& = A_0(w_3^{k})+e^{2\pi i/3}\cdot w_9^kA_1(w_3^{k})+e^{-2\pi i/3}\cdot w_9^{2k}A_2(w_3^{k})
\end{aligned}
\end{equation}
$$

$$
\begin{equation}
\begin{aligned}
A(w_9^{k+6})
& = A_0(w_3^{k})+e^{-2\pi i/3}\cdot w_9^kA_1(w_3^{k})+e^{2\pi i/3}\cdot w_9^{2k}A_2(w_3^{k})
\end{aligned}
\end{equation}
$$

其中$k=0,1,2$。根据上述递推表达式，可以模仿基为2的FFT算法，进行基为3的FFT。

15. 最坏情况为$O(n)$的快速选择算法

在之前的快速选择算法中，即使我们随机选取主元，最坏情况下的复杂度仍为$O(n^2)$，下面采取一种”Median of Medians”的方法进行优化。

这个方法仅仅是改变了选取主元的方式，每次需要选取主元时：

  1. 将数组平均分成$\lceil n/5 \rceil$个子数组，每个数组5个元素，最后一个数组可能不足5个元素。
  2. 计算出$\lceil n/5 \rceil$个子数组中每个数组的中位数，生成”中位数”数组。（固定元素数目的数组中寻找中位数$O(1)$）
  3. 选择”中位数”数组的中位数作为主元。

令$p$为选取到的主元，$p$为”中位数”数组的中位数，不包括$p$所在的子数组和最后不足5元素的子数组，则至少有$\lceil\frac{1}{2}\lceil n/5\rceil \rceil-2$个子数组的中位数$m$满足$p\geq m$。由于$m$又是子数组的中位数，子数组有5个元素，所以$m\geq$3个子数组中的元素。综上所述，至少有$\lceil\frac{1}{2}\lceil n/5\rceil \rceil-2\geq3n/10-6$个元素$x$满足$p\geq x$；同理可证，至少有$3n/10-6$个元素$x$满足$p\leq x$。

根据上面的结论，令$p$作为主元，每次split()操作，最多只能把数组缩减到$7n/10+6$。列出最坏情况下的递归表达式：

$$
T(n)\leq T(\lceil n/5 \rceil)+T(7n/10+6)+O(n)
$$

使用替换法，假设$T(n)\leq cn$，则：

$$
\begin{equation}
\begin{aligned}
T(n)
& \leq T(\lceil n/5 \rceil)+T(7n/10+6)+dn \\ &\leq cn/5+c+7cn/10+6c+dn \\ &= (\frac{9}{10}c+d)n+7c
\end{aligned}
\end{equation}
$$

只要选择这样的$c$：$cn\geq (\frac{9}{10}c+d)n+7c$，就可以满足假设。

故最坏情况的复杂度是$O(n)$。

16. 3-Sum问题

在计算几何学中，很多问题都与3-Sum问题有关。给定数组$A[0,1,\cdots,n-1]$，设计算法来判断是否存在三个索引$i,j,k$使：

$$
A[i]+A[j]+A[k]=n
$$

只需要判断是否存在，不用返回具体的组合。很容易想到$O(n^2)$的算法，而且目前并没有找到比$O(n^2)$更快的算法。

但是如果施加一个约束：$0\leq A[k] \leq n,k=0,1,\cdots,n-1$，复杂度就可以被优化到$O(n\log n)$。

我们构造出下面的多项式：

$$
p(x)=x^{A[0]}+x^{A[1]}+\cdots+x^{A[n-1]}=\sum_{i=0}^{n-1}x^{A[i]}
$$

这个多项式的次数最大只可能是$n$。令$q(x)=p(x)^3$，则：

$$
q(x)=(\sum_{i=0}^{n-1}x^{A[i]})(\sum_{j=0}^{n-1}x^{A[j]})(\sum_{k=0}^{n-1}x^{A[k]})=\sum_{0\leq i,j,k<n}x^{A[i]+A[j]+A[k]}
$$

我们使用FFT计算出$q(x)$，$q(x)$的$x^n$前面的系数就是满足条件的$(i,j,k)$的组数，复杂度为$O(n\log n)$。

若没有$0\leq A[k] \leq n,k=0,1,\cdots,n-1$的约束，使用这个方法效率会很低，因为数组的元素可能很大，导致多项式乘法耗时太久。

Quick Link: 算法笔记整理

Like this article? Support the author with

Follow

Categories

Tags

Algorithms-Notes15
C++1
Cryptography1
Database1
Divide and Conquer1
FFT1
Hashing1
Internet1
Interview4
Number Theory6
Sorting1
Statistics1
Web APP1
iOS APP2
×