本章注记

1968年，Knuth发表了总标题为《计算机程序设计艺术》［209，210，211］的三卷著作中的第1卷。第1卷引领了现代计算机算法的研究，使之聚焦于运行时间的分析。对这里给出的许多主题，这3卷著作仍然是有吸引力的且有价值的参考书。依照Knuth的说法，“算法”这个词来源于9世纪一位波斯数学家的名字“al-Khowrizm”。

Aho、Hopcroft和Ullman［5］提倡使用第3章引入的记号，包括Θ记号，把算法的渐近分析作为比较相对性能的一种方法。他们还推广了使用递归关系来描述递归算法的运行时间。

Knuth［211］提供了许多排序算法的一种百科全书似的处理。他对各种排序算法的比较包括精确的执行步数分析，这种分析类似于我们这里对插入排序所做的分析。Knuth对插入排序的讨论包括该算法的几种变形。其中最重要的是由D.L.Shell提出的Shell排序，它对输入序列的周期性子序列使用插入排序，结果形成了一种更快的排序算法。

Knuth还描述了归并排序。他提到在1938年就有人发明了一种机械排序装置，能够在一趟内合并两组穿孔卡片。计算机科学的先驱之一J.von Neumann显然于1945年在计算机EDVAC上为归并排序编写过一个程序。

Gries［153］描述了证明程序正确性的早期历史，他把该领域的第一篇文章归功于P.Naur，并把循环不变式归功于R.W.Floyd。Mitchell［256］编写的教材中描述了证明程序正确性的一些更新的进展。