算法(4th ed)(196):基础——算法分析 6.13

阅读数:9 2019 年 11 月 9 日 15:44

算法(4th ed)(196):基础——算法分析 6.13

(提高题)

1.4.14 4-sum。为 4-sum 设计一个算法。

1.4.15 快速 3-sum。作为热身,使用一个线性级别的算法(而非基于二分查找的线性对数级别的算法)实现 TwoSumFaster 来计算已排序的数组中和为 0 的整数对的数量。用相同的思想为 3-sum 问题给出一个平方级别的算法。

1.4.16 最接近的一对(一维)。编写一个程序,给定一个含有 Ndouble 值的数组 a[],在其中找到一对最接近的值:两者之差(绝对值)最小的两个数。程序在最坏情况下所需的运行时间应该是线性对数级别的。

1.4.17 最遥远的一对(一维)。编写一个程序,给定一个含有 Ndouble 值的数组 a[],在其中找到一对最遥远的值:两者之差(绝对值)最大的两个数。程序在最坏情况下所需的运行时间应该是线性级别的。

1.4.18 数组的局部最小元素。编写一个程序,给定一个含有 N 个不同整数的数组,找到一个局部最小元素:满足 a[i]<a[i1],且 a[i]<a[i+1] 的索引 i。程序在最坏情况下所需的比较次数为 2lgN

:检查数组的中间值 a[N/2] 以及和它相邻的元素 a[N/2-1]a[N/2+1]。如果 a[N/2] 是一个局部最小值则算法终止;否则则在较小的相邻元素的半边中继续查找。

1.4.19 矩阵的局部最小元素。给定一个含有 N2 个不同整数的 N×N 数组 a[]。设计一个运行时间和 N 成正比的算法来找出一个局部最小元素:满足 a[i][j]<a[i+1][j]a[i][j]<a[i][j+1]a[i][j]<a[i-1][j] 以及 a[i][j]<a[i][j-1] 的索引 ij。程序的运行时间在最坏情况下应该和 N 成正比。

1.4.20 双调查找。如果一个数组中的所有元素是先递增后递减的,则称这个数组为双调的。编写一个程序,给定一个含有 N 个不同int 值的双调数组,判断它是否含有给定的整数。程序在最坏情况下所需的比较次数为 3lgN

1.4.21 无重复值之中的二分查找。用二分查找实现 StaticSETofInts(请见表 1.2.15),保证 contains() 的运行时间为 lgR,其中 R 为参数数组中不同整数的数量。

1.4.22 仅用加减实现的二分查找(Mihai Patrascu)。编写一个程序,给定一个含有 N 个不同 int 值的按照升序排列的数组,判断它是否含有给定的整数。只能使用加法和减法以及常数的额外内存空间。程序的运行时间在最坏情况下应该和 logN 成正比。

:用斐波纳契数代替 2 的幂(二分法)进行查找。用两个变量保存 FkFk1 并在 [i,i+Fk] 之间查找。在每一步中,使用减法计算 Fk2,检查 i+Fk2 处的元素,并根据结果将搜索范围变为 [i,i+Fk2] 或是 [i+Fk2,i+Fk2+Fk1]

1.4.23 分数的二分查找。设计一个算法,使用对数级别的比较次数找出有理数 p/q,其中 0<p<q<N,比较形式为给定的数是否小于 x提示:两个分母均小于 N 的有理数之差不小于 1/N2

1.4.24 扔鸡蛋。假设你面前有一栋 N 层的大楼和许多鸡蛋,假设将鸡蛋从 F 层或者更高的地方扔下鸡蛋才会摔碎,否则则不会。首先,设计一种策略来确定 F 的值,其中扔 lgN 次鸡蛋后摔碎的鸡蛋数量为 lgN,然后想办法将成本降低到 2lgF

1.4.25 扔两个鸡蛋。和上一题相同的问题,但现在假设你只有两个鸡蛋,而你的成本模型则是扔鸡蛋的次数。设计一种策略,最多扔 2N 次鸡蛋即可判断出 F 的值,然后想办法把这个成本降低到 cF 次。这和查找命中(鸡蛋完好无损)比未命中(鸡蛋被摔碎)的成本小得多的情形类似。

1.4.26 三点共线。假设有一个算法,接受平面上的 N 个点并能够返回在同一条直线上的三个点的组数。证明你能够用这个算法解决 3-sum 问题。强烈提示:使用代数证明当且仅当 a+b+c=0 时 (a,a3)(b,b3)(c,c3) 在同一条直线上。

1.4.27 两个栈实现的队列。用两个栈实现一个队列,使得每个队列操作所需的堆栈操作均摊后为一个常数。提示:如果将所有元素压入栈再弹出,它们的顺序就被颠倒了。如果再次重复这个过程,它们的顺序则会复原。

1.4.28 一个队列实现的栈。使用一个队列实现一个栈,使得每个栈操作所需的队列操作数量为线性级别。提示:要删除一个元素,将队列中的所有元素一一出列再入列,除了最后一个元素,应该将它删除并返回(这种方法的确非常低效)。

1.4.29 两个栈实现的 steque。用两个栈实现一个 steque(请见练习 1.3.32),使得每个 steque 操作所需的栈操均摊后为一个常数。

1.4.30 一个栈和一个 steque 实现的双向队列。使用一个栈和 steque 实现一个双向队列(请见练习 1.3.32),使得双向队列的每个操作所需的栈和 steque 操作均摊后为一个常数。

1.4.31 三个栈实现的双向队列。使用三个栈实现一个双向队列,使得双向队列的每个操作所需的栈操作均摊后为一个常数。

1.4.32 均摊分析。请证明,对一个基于大小可变的数组实现的空栈的 M 次操作访问数组的次数和 M 成正比。

1.4.33 32 位计算机中的内存需求。给出 32 位计算机中IntegerDateCounterint[]double[]double[][]StringNodeStack(链表表示)对象所需的内存,设引用需要 4 字节,表示对象开销为 8 字节,所需内存均会被填充为 4 字节的倍数。

1.4.34 热还是冷。你的目标是猜出 1 到 N 之间的一个秘密的整数。每次猜完一个整数后,你会知道你的猜测和这个秘密整数是否相等(如果是则游戏结束)。如果不相等,你会知道你的猜测相比上一次猜测距离该秘密整数是比较热(接近)还是比较冷(远离)。设计一个算法在 2lgN 之内找到这个秘密整数,然后再设计一个算法在 1lgN 之内找到这个秘密整数。

1.4.35 下压栈的时间成本。解释下表中的数据,它显示了各种下压栈的实现的一般时间成本,其中成本模型会同时记录数据引用的数量(指向被压入栈之中的数据的引用,指向的可能是数组,也可能是某个对象的实例变量)和被创建的对象数量。

下压栈(的各种实现)的时间成本

数据结构元素类型压入 Nint 值的成本
数据的引用创建的对象
基于链表int2NN
Integer3N2N
基于大小可变的数组int5NlgN
Integer5NN

1.4.36 下压栈的空间成本。解释下表中的数据,它显示了各种下压栈的实现的一般空间成本,其中链表的节点为一个静态的嵌套类,从而避免非静态嵌套类的开销。

下压栈(的各种实现)的空间成本

数据结构元素类型Nint 值所需的空间(字节)
基于链表int32N
Integer56N
基于大小可变的数组int4N16N 之间
Integer32N56N 之间

评论

发布