算法(4th ed)(195):基础——算法分析 6.12

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

算法(4th ed)(195):基础——算法分析 6.12

(练习)

1.4.1 证明从 N 个数中取三个整数的不同组合的总数为 N(N1)(N2)/6提示:使用数学归纳法。

1.4.2 修改 ThreeSum,正确处理两个较大的 int 值相加可能溢出的情况。

1.4.3 修改 DoublingTest,使用 StdDraw 产生类似于正文中的标准图像和对数图像,根据需要调整比例使图像总能够充满窗口的大部分区域。

1.4.4 参照表 1.4.4 为 TwoSum 建立一张类似的表格。

1.4.5 给出下面这些量的近似:

a. N+1

b. 1+1/N

c. (1+1/N)(1+2/N)

d. 2N315N2+N

e. lg(2N)/lgN

f. lg(N2+1)/lgN

g. N100/22

1.4.6 给出以下代码段的运行时间的增长数量级(作为 N 的函数):

a.

复制代码
int sum = 0;
for (int n = N; n > 0; n /= 2)
for(int i = 0; i < n; i++)
sum++;

b.

复制代码
int sum = 0;
for (int i = 1; i < N; i *= 2)
for (int j = 0; j < i; j++)
sum++;

c.

复制代码
int sum = 0;
for (int i = 1; i < N; i *= 2)
for (int j = 0; j < N; j++)
sum++;

1.4.7 以统计涉及输入数字的算术操作(和比较)的成本模型分析 ThreeSum。

1.4.8 编写一个程序,计算输入文件中相等的整数对的数量。如果你的第一个程序是平方级别的,请继续思考并用 Array.sort() 给出一个线性对数级别的解答。

1.4.9 已知由倍率实验可得某个程序的时间倍率为 2b 且问题规模为 N0 时程序的运行时间为 T,给出一个公式预测该程序在处理规模为 N 的问题时所需的运行时间。

1.4.10 修改二分查找算法,使之总是返回和被查找的键匹配的索引最小的元素(且仍然能够保证对数级别的运行时间)。

1.4.11 为 StaticSETofInts(请见表 1.2.15)添加一个实例方法 howMany(),找出给定键的出现次数且在最坏情况下所需的运行时间和 logN 成正比。

1.4.12 编写一个程序,有序打印给定的两个有序数组(含有 Nint 值)中的所有公共元素,程序在最坏情况下所需的运行时间应该和 N 成正比。

1.4.13 根据正文中的假设分别给出表示以下数据类型的一个对象所需的内存量:

a. Accumulator

b. Transaction

c. FixedCapacityStackOfStrings,其容量为 C 且含有 N 个元素

d. Point2D

e. Interval1D

f. Interval2D

g. Double

评论

发布