辛未羊的网络日志

需求

我的网站托管在VPS上，使用Nginx提供服务。Nginx的日志中大多数是搜索引擎爬虫和DNS服务器的访问记录，真实用户的只占一小部分。我想把真实用户的访问记录提取出来，这样便能获得比Google Analytics更详细的统计信息。

引子

最近看到有网友发表了一个看法，原文如下：

當你知道了許多東南亞國家中學開始，理化就是用英文授課，跟英美無縫接軌，你會不會感覺中文世界的孩子未來堪憂?

本科毕业以后，我断断续续背过好几次单词，持续时间长的有一个多月，短的只有几天。虽然几次都半途而废，没有长期坚持，但还是有作用的，我的词汇量从4500提升到了现在的7000左右。

代码

最近用LaTeX的beamer文档类做了一个中文幻灯片，输出pdf格式的文档。文档结构清晰，数学公式非常漂亮，也有动态分步显示内容的功能，演示效果很不错。在这里把我的模板分享给有需要的人。

主要内容

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

主要内容

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

起因

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

主要内容

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

主要内容

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

主要内容

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