辛未羊的网络日志

主要内容

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

主要内容

由于概率算法在实际中用得不多，我先战略性地快速过完本章。分析一个随机算法的运行时间时，输入值由随机数生成器产生，运行时间称为期望运行时间。指示器随机变量为概率和期望之间的转换提供了一个便利的方法，用于很多随机算法的分析中。

起因

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

主要内容

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

主要内容

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

主要内容

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

主要内容

本章介绍了算法的定义、作用和重要性。简单地说，算法（algorithm）是定义良好的计算过程。算法是一系列的计算步骤，用来将输入数据转换成输出结果。算法能够解决各种类型的问题，应用面很广。

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

STL

本书的开头，千言万语汇成一句话：STL很牛逼。STL有多种实现，本书剖析的SGI版本可读性很好，也是被GCC使用的版本。

起因

最近学会了五笔输入法。我学的是新世纪版，因版权原因，网络上的码表资源不多，很多爱好者都自己制作码表，而且很少对外传播。作为程序员，写代码生成码表自然不在话下，于是我用C++写了个五笔码表管理工具RimeWubiDictMngr。