Fundamental Algorithm Final存档 & 解析

admin管理员组

文章数量:1612823

文章目录

• Problem 1
• Problem 2

Problem 1

思路：

• 第一题很简单，就是bottom-up的构建 2-3树，这样的复杂度是 O ( n ) O(n) O(n)，因为原来链表已经是排好序的了
• 第2题问如何构建一个只有S和T交集元素的2-3树. 也很简单.
  • 首先遍历2个树，这个时间复杂度是 O ( S + T ) O(S+T) O(S+T). 遍历2-3树的所有叶子节点的时间复杂度是 O ( n ) O(n) O(n).
  • 然后，求交集. 因为遍历之后得到的两个序列一定是order的，所以可以再次直接遍历这2个array，用 two-finger，2个指针分别指向2个array头. 大致pseudo-code如下，就和merge sort中的merge步骤一样：

i = 0, j = 0
while (i < S.length && j < T.length) {
	if (S[i] < T[j)
		res[k++] = S[i++];
	else if (S[i] > T[j])
		res[k++] = T[j++];
	else {
		res[k++] = S[i];
		++i;
		++j;
	}
}
while (i < S.length) { res[k++] = S[i++]; }
while (j < T.length) { res[k++] = T[j++];}

• 得到交集元素后，再次build 2-3 tree，还是bottom-up. ruuning time is O ( S ∩ T ) O(S\cap T) O(S∩T) 这个时间复杂度一定是小于 O ( S + T ) O(S+T) O(S+T)的，所以总体就是 O ( S + T ) O(S+T) O(S+T).

标答如下：

1. Work from the bottom up. Go through the items in W W W in groups of 3 and create a parent node for those 3. At the end, if you get to the point where there are 4 items left group them in two groups of 2; if you get to the point where this are 2 items left, group them together; otherwise, you can group all the items in 3. Keep iterating at higher levels until you reach the root. The total time spent is proportional to the total number of nodes in the tree, and the total number of nodes in the tree is less than twice the number of leaves (actually about 3/2 the number of leaves.)

   To assign the keys in the internal nodes, the naive algorithm is to loop through the internal nodes and find the smallest values in the second and third subtrees. The total time is the sum over the internal nodes N N N of the distances from N N N to the bottom of the tree. But, as we argued in the analysis of building a min-heap bottom up, that sum is linear in W W W.

2. Enumerate the elements of S S S and T T T by doing depth-first searches through the trees.
   Use the two-fingered method to compute S ∩ T S ∩ T S∩T. Turn S ∩ T S ∩ T S∩T into a 2-3 tree using the method of part A.

Problem 2

大概意思就是要构造2个函数

• Precompute() 输入原来的m x n的数组，然后重新建一个新的数据结构. 复杂度 O ( m n ) O(mn) O(mn)
• SumBox(D, a, b, c, d)，输入新 create 的数据结构，以及4个int表示一个子矩阵 subbox，返回这个subbox 里元素的和. 这个函数复杂度 O ( 1 ) O(1) O(1)

point: array 是 1-indexing

思路：

1. 首先，SumBox()函数的running time是常数，意味着一定是不需要遍历D的操作的，肯定是直接取D中几个数计算一下就行
2. 那么思考，这个D到底是什么？很大概率就是和A size一样的二维数组，不然SumBox()函数传入的 a, b, c, d 表示原本A中的subbox，如果 D 和 A 不一样，则还要转换一下
3. 那么有了2的猜测，就可以思考 D[i][j] 表示什么了？最简单的就是从左上角元素开始到(i, j)坐标为止的subbox的 sum 值；这样的话SumBox()函数就是返回D[b][d] - D[a][d] - D[b][c] + D[a][c], running time O ( 1 ) O(1) O(1)
4. 那么确认一下，Precompute()复杂度是多少？我们只需要遍历一遍原始array A，就可以得到D

标准答案如下：

total 8 problems, 剩余待补

本文标签： algorithmfundamentalampfinal