程序设计导论：Python语言实践

4.1.2　假说

在计算机科学的早期，唐纳德·克努特（Donald Knuth）证明了如下观点：尽管在理解程序的运行时间上存在各种复杂的因素，但是从原则上而言，可以建立准确的模型帮助我们精确地预测一个特定程序的运行时间。对这类问题的正确分析包含如下内容：

·透彻理解程序

·透彻理解系统和计算机

·数学分析的高级工具

因此，这种工作最好留给专家们。然而，每一个程序员都需要知道如何做出粗略的性能估计。幸运的是，通过组合使用经验观察和一小部分数学工具集合，我们常常可以获取这些知识。

程序4.1.1　三数和问题（threesum.py）

程序4.1.1从标准输入读取一个整数数组，向标准输出写入数组中三个数和为0的个数。如果个数较小（<10），则同时输出满足条件的三个数。文件1000ints.txt中包含1000个随机32位整数（取值范围从-2³¹到2³¹-1）。这个文件中不太可能包括这种类型（三个数和为0）的三个元组（triple）（具体参见本节习题第27题）。程序4.1.1的运行过程和结果如下：

1. 倍增假说（Doubling hypothesis）

对于许多程序，我们可以基于如下问题建立一个假说：如果输入的大小加倍，对程序的运行时间有什么影响？为了简洁起见，我们称这种假说为倍增假说。也许关注成本最简单的方法就是在程序开发过程和实际应用中问自己这个问题。接下来，我们将讨论如何通过科学方法解答这个问题。 ...