0%

主要内容

本章介绍堆排序(heapsort)算法。

堆排序算法的复杂度和归并排序相同,但是仅需要常数个额外的元素空间存储临时数据。堆(heap)不仅仅用在堆排序中,还可以构造一种有效的优先队列(priority queue)。

阅读全文 »

主要内容

由于概率算法在实际中用得不多,我先战略性地快速过完本章。

分析一个随机算法的运行时间时,输入值由随机数生成器产生,运行时间称为期望运行时间。指示器随机变量为概率和期望之间的转换提供了一个便利的方法,用于很多随机算法的分析中。

阅读全文 »

缘起

在知乎上看到一篇文章:如何下载50年前中国各地的高清卫星照片,网友们纷纷撰写了各地50年前卫星照片的解读文章。我也下载到了我的家乡——湖北黄冈在1970年的卫星地图,并做简要的解读。

市区变迁

黄州是黄冈市唯一的市辖区,也是市政府所在地。明代以后,蕲州(今蕲春县)划归黄州府管理,形成与当今黄冈市类似的行政格局,基本沿袭至今。因此,明清以来,黄州一直是鄂东黄冈地区的政治经济文化中心。本文介绍的就是黄州区的卫星地图。

阅读全文 »

主要内容

本章介绍的第一个算法求解最大子序列和问题,第二个算法求解矩阵乘法问题。递归式与分治法紧密相关,本章介绍三种方法求解递归式:代入法、递归树法和主方法。

最大子序列和问题

买股票问题可以转化为最大子序列和问题。只有当序列中包含负数,最大子序列和问题才有意义。

阅读全文 »

主要内容

本章讲解如何简化算法的渐近分析,介绍了几类渐近记号。最后简单介绍了常用函数的性质。本章的内容在这里描述得非常简略,但为了保持整个系列的完整性,还是贴出来了。

渐近记号

本章介绍了如下渐近记号,它们的严格定义分别如下:

阅读全文 »

主要内容

本章介绍了一个贯穿全书的算法设计与分析的框架。正文中介绍了插入排序和归并排序两种排序算法,以它们为例,介绍了用循环不变式证明算法正确性的方法和分治法的思想。还介绍了如何分析算法的运行时间。

插入排序

本书介绍的第一个算法是插入排序算法。插入排序的工作机理和很多人打牌时,整理手中牌时的做法差不多。它的基本思想是,通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。根据伪代码,给出如下的C语言实现:

阅读全文 »

主要内容

本章介绍了算法的定义、作用和重要性。

简单地说,算法(algorithm)是定义良好的计算过程。算法是一系列的计算步骤,用来将输入数据转换成输出结果。算法能够解决各种类型的问题,应用面很广。计算机的计算资源和存储资源是有限的,时间和空间上有效的算法能够有效地利用这些有限的资源。解决同一问题的不同算法,效率常常相差很大,这种效率上差距的影响往往比硬件和软件的差距还要大。拥有扎实的算法知识和技术基础对程序员来说非常重要。

阅读全文 »

下面是一个优秀的程序员应该掌握的基础知识以及较为靠谱的学习路线:

  • 计算机体系架构:读《深入理解计算机系统》,做完Lab Assignments
  • 数据结构与算法:读《算法导论》,做完习题
  • 操作系统:读《现代操作系统》和《操作系统概念》中的任何一本,跟着MIT 6.824课程,把xv6撸一遍
阅读全文 »

东坡先生作有一曲《望江南·超然台作》,词云:

春未老,风细柳斜斜。试上超然台上望,半壕春水一城花。烟雨暗千家。 寒食后,酒醒却咨嗟。休对故人思故国,且将新火试新茶。诗酒趁年华。

诗酒趁年华,东坡先生道:不要荒废了这大好的年华,就应该饮酒作诗才不算辜负时光。

阅读全文 »

OpenGrok是跨平台、开源免费的源码阅读工具。OpenGrok生成源码的索引,Apache Tomcat提供Web服务,用户即可在浏览器中阅读代码,使用体验可以去看看这里。Linux下好用的源码阅读工具极少,OpenGrok可以一试。

本文是一篇没有技术含量的笔记,之所以贴出来是因为我找到的其它教程都失效了。

阅读全文 »