我们先提出几个问题. 

Problem 1.1
试用最快的方法找到给定五个两两不同的数的中位数.

Problem 2.1
试求基于比较的排序的时间复杂度的下确界.

Problem 3.1
现在有一个序列, 其只包含0, 1, 2三种元素. 那么, 在只允许额外申请常数空间的前提下, 试求最快的对这个序列排序的方法. 

对Problem 1.1的思考有助于我们引入比较, 排列, 和排序的概念. 对于Problem 2.1来说, 我们将一般性地探讨一下基于比较的排序的原理和复杂度分析, 从而在得出结论的同时给出详细的说明.

我们将在本文的最后部分解决Problem 3.1这一个特殊的排序问题. 在此基础上, 我们将探讨一下不基于比较的排序的原理和复杂度分析, 以及适用范围.

我的博客的上一个系列, 即"算法漫谈"系列, 于两年前的夏天已经完结. 此后繁忙于诸事, 亦无暇打理博客空间. 偶有读者反馈一些问题, 我便逐个修复. 

然而近两年, 助教工作已成为我工作中不可少的一部分. 我助教的课程涵盖Programming Languages (内容主要涵盖编程语言的类型化定义和函数式类型方法, 区别于'学习一门编程语言'的课程), 计算机理论, 编译原理, 和算法, 受众也从本科生, 硕士生涵盖到博士生. 这时我便有一种想法, 即把助教工作中的一些知识点和自己对数据结构与算法的认识结合起来, 写一些东西放在博客上.

加之近日, 身边有不少同学和朋友也在频繁更新博客. 我在浏览他们的文章同时, 再次感到书写博客对于梳理一些心情杂感, 或是强化对一些知识点的认识, 亦或是与身边的同学朋友的交流, 都是有一定帮助的.

​闲暇之余, 我决定再重新开启一个系列, 名为"算法精讲"系列, 从自己几年来的助教经验以及对数据结构和算法的知识出发, 谈一谈在计算机领域应用比较广泛的几类算法, 也顺便解答几道算法题目, 希望可以与同在计算机领域学习或工作的读者产生一些共鸣. 

在前文中, 我们谈到了定义在半环上的动态规划及其适用范围, 以及动态规划在图模型中的一些应用。本文我们将沿着这个思路继续探索, 并把目光从图模型转向树结构. 我们首先提出以下几个问题:

Problem 1.1
试判定一个字符串是否属于一个上下文无关文法生成的语言. 

Problem 1.2
给定一个字符串和一个随机上下文无关文法 (PCFG) , 则按照 PCFG 中的某个生成方式生成该字符串会有一个概率 p . 试求 p 的最大值. 

本文将对上述问题展开讨论. 在涉及分析树的内容之前, 我们先对前文的内容做一个小小的总结, 之后我们解决上述的两个问题. 除此之外, 我们还将提及一个数据库系统中的查询模型. 笔者的研究不涉及数据库领域的很多内容, 对这个模型的理解也比较粗浅, 在这里只是提供一个树结构上的算法思路. 

Problem 2.1 
现在有一个数据库系统, 其中不同的机器存储不同的数据. 试设计一个查询系统, 使得用户可以在最短的时间内查询到特定的数据被存储在哪个机器. 

Problem 2.2
弱化Problem 2.1的需求. 现在我们查询特定的数据后, 允许得到一个机器的列表, 只要列表中存在一个机器存有我们所需的数据即可. 试优化这个查询系统. 

最近在 <Artificial Intelligence> 这门课的课程论文上写了一个 survey , 主要涉及了一些常见的寻路问题, 包括寻找最短路径的若干问题,寻找第 k 短路径的若干问题以及未知全局的寻路问题. 本来想把论文的内容翻译出来贴在博客上, 后来发现和之前的几篇博文有一部分重复的地方, 只有几个算法在博客中没有提到. 于是决定把摘要目录翻译一下, 另直接把文章贴出来和大家分享.

我们先提出与"回路"有关的几个问题.

problem 1.1
试分析存在回路的状态空间对动态规划是否具有适用性.

problem 2.1
在一个无负回路的图中有两个节点 s, t, 试求两点间的第 k 短路径.

对于第一个问题, 我们将沿着半环上的动态规划继续走下去, 探讨一下非幂等半环上的动态规划问题, 从而给出动态规划的一个更为广义的适用范围; 对于后面一个问题, 我们将从 Dijkstra 算法的适用性谈起, 并分析几个典型的最短路径问题的算法, 最后给出一个普适的求前 k 短路径的算法和一个非常漂亮的 k 最优 Dijkstra 算法, 来完成这个问题的解答.