算法(4th ed)(148):基础——算法分析 6.2.1

阅读数:10 2019 年 11 月 6 日 07:42

算法(4th ed)(148):基础——算法分析 6.2.1

(观察:举例)

右侧的 ThreeSum 程序是一个可运行的示例。它会统计一个文件中所有和为 0 的三整数元组的数量(假设整数不会溢出)。这种计算可能看起来有些不自然,但其实它和许多基础计算性任务都有着深刻的联系(例如,请见练习 1.4.26)。作为测试输入,我们使用的是本书网站上的 1Mints.txt 文件。它含有 100 万个随机生成的 int 值。1Mints.txt 中的第二个、第八个和第十个元组的和均为 0。文件中还有多少组这样的数据?ThreeSum 能够告诉我们答案,但它所需的时间可以接受吗?问题的规模 N 和 ThreeSum 的运行时间有什么关系?我们的第一个实验就是在计算机上运行 ThreeSum 并处理本书网站上的 1Kints.txt、2Kints.txt、4Kints.txt 和 8Kints.txt 文件,它们分别含有 1Mints.txt 中的 1000、2000、4000 和 8000 个整数。你可以很快得到这样的整数元组在 1Kints.txt 中共有 70 组,在 2Kints.txt 中共有 528 组,如图 1.4.1 所示。这个程序需要用比之前长得多的时间得到在 4Kints.txt 中共有 4039 组和为 0 的整数。在等待它处理 8Kints.txt 的时候,你会发现你在问自己:“我的程序还要运行多久?”你会看到,对于这个程序,回答这个问题很简单。实际上,你常常能在程序运行的时候就给出一个较为准确的预测。

复制代码
public class ThreeSum
{
public static int count(int[] a)
{ // 统计和为 0 的元组的数量
int N = a.length;
int cnt = 0;
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
for (int k = j+1; k < N; k++)
if (a[i] + a[j] + a[k] == 0)
cnt++;
return cnt;
}
public static void main(String[] args)
{
int[] a = In.readInts(args[0]);
StdOut.println(count(a));
}
}
对于给定的 `N`,这段程序需要运行多长时间
复制代码
% more 1Mints.txt
324110
-442472
626686
-157678
508681
123414
-77867
155091
129801
287381
604242
686904
-247109
77867
982455
-210707
-922943
-738817
85168
855430
...

算法(4th ed)(148):基础——算法分析 6.2.1

图 1.4.1 记录一个程序的运行时间

评论

发布