《算法导论(原书第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
1409
分享
相关文章
python实现樱花
python实现樱花
1741 0
Python实现张万森下雪了的效果
Python实现张万森下雪了的效果
110 0
hdu1181 变形课(暴力搜索法)
hdu1181 变形课(暴力搜索法)
48 0
【洛谷算法题】B2029-大象喝水【入门1顺序结构】
【洛谷算法题】B2029-大象喝水【入门1顺序结构】
【算法竞赛】实现约瑟夫问题的四种方法(附手绘图详解)
【算法竞赛】实现约瑟夫问题的四种方法(附手绘图详解)
267 1
Plant(快速幂+数学分析(没想到吧,数学无处不在))
Plant(快速幂+数学分析(没想到吧,数学无处不在))
94 0
蓝桥杯2020省赛真题J 怪物猎人 装饰珠 问题(C++解法)(上)
蓝桥杯2020省赛真题J 怪物猎人 装饰珠 问题(C++解法)(上)
304 0
蓝桥杯2020省赛真题J 怪物猎人 装饰珠 问题(C++解法)(上)
蓝桥杯练习题三 - 纸牌三角形(c++)
蓝桥杯练习题三 - 纸牌三角形(c++)
154 0
AI助理

你好,我是AI助理

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