算法导论14.1节习题解答

算法导论习题解答系列停了一年了,现在重新拾起,好多算法已经忘了,有的记得大概,但是真正的用代码实现却很难下手。

14.1-3 写出OS-SELECT的非递归形式
一般递归形式改写为非递归形式要用到while,有时还要用到栈结构。

OS-SELECT(x, i){ r = size[left[x]] + 1; while (r != i) { if (i < r) { x = left[x]; r = size[left[x]] + 1; } else { x = right[x]; i = i –r; r = size[left[x]] + 1; } } return x;}

14.1-4 写出一个递归过程OS-KEY-RANK(T, k)

int OS-KEY-RANK(T, k){ if (k == key[root[T]]) return size[left[root[T]]] + 1; else if (k < key[root[T]]) return OS-KEY-RANK(left[root[T]], k); else return OS-KEY-RANK(right[root[T]], k) + size[left[root[T]]] + 1;}

14.1-5 确定元素x的第i个后继,时间为lg(n)

GET-SUCCESSOR(T, x, i){ r = OS-RANK(T, x); return OS-SELECT(root[T], r + i);}

14.1-6
在这题中,将每个结点的秩存于该结点自身之中,这个秩是相对于以该结点为根的子树而言的。
因而在插入结点x时,对于从root到x结点的路经上的所有结点y,如果插入路经经过y的左支,则rank[y]的值加1,若经过其右支,则rank[y]的值不变。
在删除结点x时,对于从root到x结点的路经上的所有结点y,如果删除路经经过y的左支,则rank[y]的值减1,若经过其右支,则rank[y]的值不变。

如图,在进行右旋转时,x的秩是不变的,node的秩变为rank[node]减去原来的rank[x]。左旋同理。

14.1-7 利用顺序统计树在O(nlgn)的时间内统计逆序对
在习题2-4中,其要求用归并排序来计算逆序对,见算法导论2-4习题解答(合并排序算法)
在这里,我们对于数组{2,3,8,6,1}这样分析,对于每个数,选取其前面的数与其比较,
对于6,与其对比的为2,3,8,逆序对有1对,记作inversion_count,
6在原数组的索引为3,记作j,
然后我们来分析子数组{2,3,8,6},6在其中的排名为3,记作rank_j;
再通过分析其他数,我们归纳如下:
inversion_count = j + 1 – rank_j
当把每个结点插入顺序统计树时,我们可以知道j的值,同时调用OS-RANK来得到rank_j,从而得到inversion_count,在这里,每插入一次,就计算一次。
由于插入和OS-RANK都是lg(n),故n个结点即为n*lg(n)。

14.1-8 现有一个圆上的n条弦,每条弦都按其端点来定义,请给出一个能在O(n*lgn)时间内确定圆内相交弦的对数的算法,假设任意两条弦都不会共享端点。

参考自http://topic.csdn.net/u/20081119/17/397cc718-f4dc-4570-9991-aee57dd73416.html
如图,对于两条弦P1Q1和P3Q3来说,圆心与端点形成的向量有一个角度A
如果A(P1)<A(P3)<A(Q1)<A(Q3)或者A(P3)<A(P1)<A(Q3)<A(Q1),这样角度区间“交叉”就意味着两条弦有交叉。

由于有n条弦,故有2n个端点,每个端点的取值范围为[0, 2*pi),对这2n个端点按角度值进行从小到大排序,排序的时间复杂度为O(n*lgn),所得数组为A[1…2n]
然后建立一个顺序统计树,起先为空,先插入A[1],它为一条弦的起始端点,然后遇到其他弦的起始端点就插入,当遇到一条弦的终端点时,就统计在该树中大于该弦的起始端点角度值的端点个数,之后就从树中删除该弦的两个端点。
如图,先插入P1,再插入P2,再插入P3,再插入P4,再插入Q4,Q4为弦P4Q4的终端店,故停止插入,开始统计树中大于P4角度值的端点个数,为0,然后删除P4与Q4。
再插入Q2,为终端点,统计此时树中大于P2端点值的个数,为1个,然后删除P2与Q2。
再插入Q1,为终端点,统计此时树中大于P1端点值的个数,为1个,然后删除P1与Q1。
再插入Q3,为终端点,统计此时树中大于P3端点值的个数,为0个,然后删除P3与Q3。
结束,统计结果一共为2,与图中相符。
在这里,要用到顺序统计树的插入、删除操作,以及OS-RANK函数。每个操作都为O(lgn)的时间复杂度,有2n个结点,故时间复杂度仍是O(n*lgn)。

本文链接



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量