算法(4th ed)(197):基础——算法分析 6.14

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

算法(4th ed)(197):基础——算法分析 6.14

(实验题)

1.4.37 自动装箱的性能代价。通过实验在你的计算机上计算使用自动装箱和自动拆箱所付出的性能代价。实现一个 FixedCapacityStackOfInts,并使用类似 DoublingRatio 的用例比较它和泛型 FixedCapacityStack<Integer> 在进行大量 push()pop() 操作时的性能。

1.4.38 3-sum 的初级算法的实现。通过实验评估以下 ThreeSum 内循环的实现性能:

复制代码
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
for (int k = 0; k < N; k++)
if (i < j && j < k)
if (a[i] + a[j] + a[k] == 0)
cnt++;

为此实现另一个版本的 DoublingTest,计算该程序和 ThreeSum 的运行时间的比例。

1.4.39 改进倍率测试的精度。修改 DoublingRatio,使它接受另一个命令行参数来指定对于每个 N 值调用timeTrial() 方法的次数。用程序对每个 N 执行 10、100 和 1000 遍实验并评估结果的准确程度。

1.4.40 随机输入下的 3-sum 问题。猜测找出 N 个随机int 值中和为 0 的整数三元组的数量所需的时间并验证你的猜想。如果你擅长数学分析,请为此问题给出一个合适的数学模型,其中所有值均匀地分布在 MM 之间,且 M 不能是一个小整数。

1.4.41 运行时间。使用 DoublingRatio 估计在你的计算机上用 TwoSumFast、TwoSum、ThreeSumFast 以及 ThreeSum 处理一个含有 100 万个整数的文件所需的时间。

1.4.42 问题规模。设在你的计算机上用 TwoSumFast、TwoSum、ThreeSumFast 以及 ThreeSum 能够处理的问题的规模为 2Px103 个整数。使用 Doub lingRatio 估计 P 的最大值。

1.4.43 大小可变的数组与链表。通过实验验证对于栈来说基于大小可变的数组的实现快于基于链表的实现的猜想(请见练习 1.4.35 和练习 1.4.36)。为此实现另一个版本的 DoublingRatio,计算两个程序的运行时间的比例。

1.4.44 生日问题。编写一个程序,从命令行接受一个整数 N 作为参数并使用StdRandom.uniform() 生成一系列 0 到 N1 之间的随机整数。通过实验验证产生第一个重复的随机数之前生成的整数数量为 πN/2

1.4.45 优惠券收集问题。用和上一题相同的方式生成随机整数。通过实验验证生成所有可能的整数值所需生成的随机数总量为 NHN

评论

发布