《算法导论(原书第3版)》一本章注记

简介: 本节书摘来自华章出版社《算法导论(原书第3版)》一 书中的第2章,第2.5节,作者:(美)Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein,更多章节内容可以访问云栖社区“华章计算机”公众号查看。

本章注记

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]编写的教材中描述了证明程序正确性的一些更新的进展。

目录
打赏
0
0
0
0
1408
分享
相关文章
|
12月前
|
Python技术分享:使用穷举法解决鸡兔同笼问题
Python技术分享:使用穷举法解决鸡兔同笼问题
447 1
为什么程序员用笛卡尔心形曲线告白的人,都还是单身?
为什么程序员用笛卡尔心形曲线告白的人,都还是单身?
266 0
为什么程序员用笛卡尔心形曲线告白的人,都还是单身?
LeetCode每日一题——790. 多米诺和托米诺平铺
有两种形状的瓷砖:一种是 2 x 1 的多米诺形,另一种是形如 “L” 的托米诺形。两种形状都可以旋转。
167 0
LeetCode每日一题——790. 多米诺和托米诺平铺
蓝桥杯练习题三 - 纸牌三角形(c++)
蓝桥杯练习题三 - 纸牌三角形(c++)
151 0
牛客 小乐乐学数学(扫描线+树状数组)
牛客 小乐乐学数学(扫描线+树状数组)
115 0
《算法导论(原书第3版)》一本章注记
本节书摘来自华章出版社《算法导论(原书第3版)》一 书中的第3章,第3.4节,作者:(美)Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
1225 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等