Dedication

　　我想我已经好久都没写日志了，因为每天都会学到太多的新东西，虽然想记录下来，但实在是有心无力——太耗时间。不过我想仍然有里程碑意义的成果必须记录下来。这个同步率改 v0.3 就是一个。

　　Bangumi 番组计划有一个可以内置的查看用户间同步率的功能，但是这个功能很简陋，也很不科学。我通过爬取 Bangumi 用户作品收藏信息，计算出了比较科学一点的同步率，使得品味相近的用户可以互相认识。

　　稍有常识的人就会看出，这实际上就是一个推荐系统嘛：推荐与你相似的用户。但是目前的同步率改不能完全算是一个推荐系统，只能说起到了某些推荐系统的功能而已。现在的“同步率改”之所以还保留着“同步率”的称法，是为了让 BGMer 在旧同步率和新同步率之间保持无缝概念接受：如果我没有标注某部作品，那么这部作品不应该在同步率上有所贡献。所以在到目前为止，所有的同步率计算都是在作品空间中进行的而非概念空间。

　　同步率改的 v0.2.1 版是一个比较基本的推荐系统实现：提取用户的所有评分并减去其平均值，得到用户对作品的偏好程度。同时对于用户没有评分的作品，利用这个作品所处于的五个状态——想看、在看、看过、搁置和抛弃——加上一定评分偏置。同时为了防止只有很少评分的用户影响系统表现，系统做了不少 trick，如评分在标准差在零点几以下的用户同步率无视评分、收藏小于 3 的用户无视评分等。这样的设计方法虽然整体思路是正确的，但是存在 ad hoc 太多、评分偏置单一的现象。

　　同时，在 Bangumi 社区交流的过程中，我发现用户对于不同类型的作品评分有一定的独立性。对于动画和三次元的评分准则，有些用户将其与音乐、书籍类作品相独立看待。

　　基于这样的事实，我在 v0.2.1 的基础上进行了大量修改，其结果就是 v0.3。他们一脉相承的特点都是：相似度在作品空间中计算，每位用户的向量都以其自己平均分为基准，对已收藏但未评分作品根据作品收藏状态有一定偏置。但是 v0.3 使用了子空间分解技术估计用户已收藏和未评分作品的评分。同时，不同类型作品的同步率分开计算，最后整合在一起形成综合同步率。

评分估计模型

　　我们记 Bangumi 某一类型（比如动画）作品的 user-item utility matrix 为 $R$，其是一个 $M \times N$ 的矩阵，其中用户数为 $M$，作品数为 $N$。矩阵的元素是元素所在行对应的用户评分减去该用户评分的平均值。用户未评分的元素值记为 0。我们的目的，就是要对某一个用户已标记未评分、收藏状态为 $s$ 的作品进行评分预估：

　　其中 $u_{i}$ 是 $M \times Q$ 的 user-concept matirx $U$ 的第 $i$ 行行向量，$v_j$ 是 $Q \times N$ 的 concept-item matrix $V$ 的第 $j$ 列列向量。$bu_{is}$ 是用户状态偏置矩阵 $Bu$ 的元素，$bi_{js}$ 是作品状态偏置矩阵 $Bi$ 的元素。得出评分估计模型的关键就是求出这四个矩阵 $U$、$V$、$Bu$ 和 $Bi$，使得 root mean square error (RMSE)最小，同时又有较好的泛化能力。

　　实际上，这个问题就是最小化 RMSE 的最优化问题。假定我们已经有了 $U$、$V$、$Bu$ 和 $Bi$ 的初始估计值，那么我们就可以通过梯度下降的方法估计出使得 RMSE 最小的局部最优解。

　　在 RMSE 的表达式中，total rated item number 是一个固定的常数，$r_{ij}$ 是已经观测到的评分。我们把最优化的目标函数写成如下形式：

　　目标函数的第一项是 RMSE，第二项是为了防止 $U$、$V$、$Bu$ 和 $Bi$ 过大的罚项。此目标函数对于行向量 $u_i$ 的导数为：

　　对于其他项的导数可以一一推得，而且计算也很简单，这里就不赘述。

　　但是目前的问题就是如何求出初始的 $U$、$V$、$Bu$ 和 $Bi$？初始值非常重要，选取一个好的初始值可以得到全局最优解。对于 $U$ 和 $V$，其是 $R$ 的一个近似分解。我们可以用 SVD 求出 $U$ 和 $V$ 的初始值。对于 $Bu$，其是一个 $M \times 5 $的矩阵，其每一行的元素是该用户处于想看、在看、看过、搁置或抛弃作品评分平均值与所有作品评分平均值之间的偏差。$Bi$ 是一个 $N \times 5$ 的矩阵，其每一行元素是该作品在 $R$ 中的不同状态中的评分平均值与 $R$ 中的总平均值之间的偏差。

泛化能力

　　我们已经推导出了变量的初始值和梯度。通过不断迭代更新 $U$、$V$、$Bu$ 和 $Bi$ 我们可以得到很低的 RMSE。但是矩阵计算量巨大，我们需要在评分系统预估的表现和现有计算能力中取得折中。到底迭代多少次、学习率为多少时合适？

　　上图是在动画类别中的 RMSE 随迭代次数变化的变化场景。我按照 7:2:1 的比例将所有动画作品评分划分为训练集、验证集和测试集（后来我发现其实这个阶段还不要用测试集）。可以看出，RMSE 在训练集上可以训练到很低，但是更多的迭代次数对验证集的 RMSE 下降作用不大。因此，我选取了在验证集 RMSE 下降曲线的第二个拐点，即迭代次数约为 70 次的位置作为迭代次数。

　　另外一个参数是学习率的选取。根据经验，学习率选取在 0.0002 时为合适。但即使如此，在计算动画类的时候，学习率在 0.0002、罚项 $\sigma^2$ 在 10 的时候还会发散。因此动画类的学习率在迭代 10 次之后，以 0.00002 的学习率继续迭代下降。

余弦距离

　　在预估出所有已收藏未评分的作品评分之后，我仍然采用余弦距离计算用户之间的同步率。正如上文所说，这样用户未收藏的作品不会影响同步率。目前阶段，我不想让用户看到某位和他/她同步率很高的人看的是完全不同的动画——尽管它们有相同的概念。

　　在同步率过去的反馈里，我总是听到有人抱怨有收藏了个位数作品的人进入了他们的前十榜单。但是，只要同步率还是采取这样的保守定义：即在作品空间的余弦距离，这种现象永远不会得到根治。

　　设想一下，如果用户 A 看过的作品是你的子集，而用户 B 看过更多的作品，他不仅看过 A 的作品，而且还看过更多的你没看过的其他作品，那么可能谁会更高？这个答案毫无疑问是 A 与你的同步率更高——尽管你可能更想让 B 在你的同步率榜单中靠前一些。也就是说，相同条件下，余弦距离的定义使得系统必然偏向收藏数目少的人。

　　鉴于这样的事实，我想同步率这个玩具，v0.3 就是它最后的一个版本了。如果要以“寻求同好”为目的，就必须抛弃“同步率”这样陈旧的概念。

下一步？

　　同步率改的设计，我想已经到达了一个里程碑了，而且我想这也完成了我对 matrix factorization 的实践。但是，寻找同好这一终极目标并没有到达。在接下来，对同好的描述可能将不是余弦距离这样直观的模型就能理解的。我已经想好了会怎么做。所以请期待下一个更棒的玩具吧。

　　此题为 CF 上的一道中等难度题。题目的原文见这里。用中文简单说一下吧：给定0到N-1的两个排列，求这两个排列的“和”。之所以会有“和”的概念出现，是因为排列的大小可以依据字典序确定。

　　所以，解决这个问题需要的两个关键步骤是：根据排列确定字典序大小；根据字典序大小还原排列。

　　一个排列和其字典序大小是有某种确定关系的。Factorial number system 就这种关系给出了理论支持。这种关系，是一种可以一一对应并且互相转换的关系。比如说，当 N=3 的时候，所有的排列和其字典序大小关系如下所示：

　　要完成互相转换的任务，必须借助于 factorial number system。这种 system 和通常的十进制、十六进制很相似，只是把“基”换成了数乘。比如说，如何表示 42，利用 factorial number system？ 4! < 42 < 5!

　　可以看到，首先 42 小于 5!，因此 42 可以由 5 以下的阶乘表示。在拆分的时候，每一位的数字不得大于当前位的阶乘数字。如$13000_{!}$的最高位为 1，1<4。各位看官可以自行拆解几个数字看看。

　　由此，我们可以把第一个表再增加一项，表示出每一个字典序大小的阶乘数系表示：

　　那么在阶乘系统下表示出来的数字，好像和排列没有明显的联系啊。好像还不如用原始的方法，就是直接从排列计算出字典序大小呢。那么这一过程怎么计算呢，用最原始的思路？比如说我们现在有排列 120。其第一个数是 1，那么在第一个数是 0 的时候就已经有了 2! 次排列。再看第二位，是 2。在 2 的前面已经有了 0 的排列（这时候就要去掉 1 了），所以其在第一位数为 1 的情况下第二位数为 2 的之前的排列有 1! 个。再看第三位，是0，这时候排序就已经确定了，加上先前的所有排列，就是 2!+1!+1=4。鉴于字典序从 0 开始计数，减去 1 即可。

　　可以看到，在使用原始方法计算字典序的时候，在计算后面的数字的时候要记住前面已经使用了什么数字（看官可以拿一个更大的排列计算一下）。因此，我们如果按照这种思路计算的话，很快就会陷入频繁的大小比较中。

　　如果我们维护一个从 1 到 N 大小的数组，每个数组元素都是 1，并且再维护一个数组，计算其部分和，就会发现，每一次确定某一位之前出现过的数字等于部分和。如果一个数字被用掉了，将其减一，相应的每一位部分和表示该位之前没有被用掉的数字个数。在阶乘系统下表示的数字的每一位，其物理意义就是部分和。我们就此举一个例子：

　　数组为(1,1,1)，部分和为(1,2,3)，排列为120。数组从 1 开始计数，为了方便，排列每一位加 1 变成 231.

• 排列第一位数字 2 索引位置对应的部分和为 2，将其记录下来，并把该位减一. 这时候数组为(1,0,1), 部分和为(1,1,2)；
• 排列第二位数字 3 索引位置对应的部分和为 2，将其记录下来，并把该位减一. 这时候数组为(1,0,0), 部分和为(1,1,1)；
• 排列第三位数字 1 索引位置对应的部分和为 1，将其记录下来，并把该位减一。

　　我们记录下来的部分和表示了在这样一个排序中，当某一位没有采用该数字的时候可选择的数字个数。由于排列已经确定，我们把记录下来的部分和减一，变成 110。这样，通过部分和，我们就可以很快计算出排列对应的阶乘系统中的数字。看官可以自己拿一个数字计算一下。

　　现在我们解决了从排列到字典序大小的转换问题，下面要解决的问题就是字典序大小到排列的转换了。如何用传统方法解决？我们可以看到阶乘系统下的数字每一位都有“部分和”的意思。同时排列的每一位数字都是不同的。利用这些信息可以从最高位推出排列。首先阶乘系统下的数字的最高位前面没有被选择的数字，它既是部分和，也是排列中的确定数字。在从排列转化为字典序的过程中，确定的数字被减一，变成不可利用，因此部分和中可以利用的部分和只有第一次出现的某个部分和————因为不可利用的数字其值为 0，在部分和中表示为没有变化。

　　假设我们现在有字典序 2，其对应的阶乘系统数字为 100，我们将其转化为 211。同样地，我们维护数组(1,1,1)和其部分和(1,2,3)。

• 阶乘系统下数字最高位为 2，部分和中第一个出现 2 的索引位置为 2，记录该位置，并将该位置减一，现在部分和为(1,1,2);
• 阶乘系统下数字次高位为 1，部分和中第一个出现 1 的索引位置为 1，记录该位置，并将该位置减一，现在部分和为(0,0,1)
• 阶乘系统下数字最低位为 1，部分和中第一个出现 1 的索引位置为 3，记录该位置。

　　看官可以发现，之所以记录下来的索引位置是不重复的，是因为每次选取第一个部分和导致了避开使用过的索引位置。记录下来的索引位置为 213，每一位减一等于 102. 看官也可以自己拿一个数字计算一下。

　　那么在实际操作中，怎么计算部分和并更新部分和呢？如果一个位置发生了改变，以后所有的部分和都要发生改变。一个直接的方法就是通过维护线段树，但是更方便的方法是使用树状数组。

　　树状数组并不直接管理部分和，而是管理某一段的和。对一个长度为 N+1 的数组，其相对应的树状数组与之等长，并且有以下性质：树状数组索引为 n 处的元素管理着索引区间为 [n-lowbit(n)+1, n] 处原始数组区间之和。所谓 lowbit，是指某一个数转化为二进制后最低非零位置转化为一个 2 的整数次方的值。其为 x & (-x)。总而言之，这个数组有着与 2 的整数次方相关联的树状组织。

　　
　　那么要计算部分和，就可以根据这个区间的信息，一块区间一块区间地叠加。可以预见，这样计算部分和的时间复杂度为 O(log n)。

　　那么如何维护树状数组？我们大可以构建一个原始数组然后在其上构建树状数组，但是鉴于这个问题的部分和是按照索引递增的，而且只在原始数组上执行加减一的操作，我们可以直接构建基于树状数组的加减一操作：在包含当前索引处的区间值加减一即可。可以预见，这样维护树状数组的时间复杂度为 O(log n)。

　　到了这里，我想解这道题所需要的所有知识已经明确了。下面是我本人写的代码：

　　总结：

1. 排列与指数系统有着一一对应的关系。排列每个数物理意义为部分和索引，指数系统每一位物理意义为部分和。
2. 树状数组每一个元素试图管理一个 2 的整数次方的大小的长度的数组，lowbit 运算可以实现这一点。

2015.01.04

Simple Binary Search

题目大意就是一种更好的 Binary Search，在一个已经排好序的数组里面找到 target，返回 target 索引。如果找不到，那么就返回 target 应该插入的位置。

我觉得还是 Acclerated C++ 那本书给了我很多启示。Binary search 的搜索区间看作是一个左闭右开区间，每次迭代的过程中，不变的准则是：区间的右边是开区间。这样可以省去考虑中间点恰好是 target 的麻烦。这样做的好处除了省去中间点的考量外，也省略掉了尾端的考虑：在 C 语言中，整数类型向 0 取整，所以 4 是 end 的话，所有小于 4 的数与之相加除以 2 的结果都必然小于 4。

当然这样没考虑区间左端。有一种情况区间左端小于 target，这时候就简单地和等于的情况合并喽。

这道题没用迭代。用迭代还可以再缩短时间。

Merge Sorted Array

给定两个已排好序的数组，把它们 merge 成一个。不要再分配空间。

按照惯常的思路是从每个数组的开头开始一一比较然后插入，但这不是 Merge Sort。其实可以从每个数组尾端开始，从大到小插入。但是这样会不会污染原有数据呢？用数学方法证明一下即可。

This week’s material is dedicated to concepts “beyond Nash Equilibrium”: iterative removal of strictly dominated strategies, minimax strategies and the minimax theorem for zero-sum game, correlated equilibria.

Different from previous weeks’ notes, I will illustrate some concepts in Chinese.

Dominated Strategies

Strictly dominated strategies are based on every player’s rationality: that is, everybody is rational, and everybody knows other players make rational decisions, and everybody knows that also… So, those strategies that are strictly dominated are to be dominated. We can get final strategy by using iterated removal.

Example 1: Prisoner’s dilemma

Follow the rational thinking, both prisoners will chose betrayal because choosing betrayal will definitely have him/her spent somewhat less time in prison in comparison to choosing cooperation. In this case, we say that betrayal dominates cooperation.

What’s interesting is that the final strategy, which is a Nash Equilibrium, is not optimal in a overall view. This is where dilemma lies, which illustrates that 非零和博弈中，帕累托最优和纳什均衡是相冲突的.

Example 2: Intelligent Pigs

The illustration of this game can be found here.

In this experiment, we can see that for the small pig, there is a dominate strategy, so the small pig would prefer waiting. After eliminating pressing for small pig, the big pig would chose to press. However, for the big pig, there is no dominate strategy, but after iterative eliminating, (wait, press) becomes the nash equilibrium.

Someone may question about the relationship between Nash equilibrium and dominant strategy equilibrium. 优势策略均衡和纳什均衡的区别在于：在优势策略均衡中，我所做的是不管你做什么，我所能做的是最好的；在纳什均衡中，我所做的是给定你所做的前提下，我所能做的是最好的，你所做的是在给定我所做的前提下你所能做的是最好的，从二者的关系可以看出，优势策略均衡是纳什均衡的一个特例，一个优势策略均衡首先是一个纳什均衡.

Maxmin Strategies and Minmax Strategies

Maxmin strategy is a strategy that maximizes one’s worst-case payoff. Maxmin Value of the game for player i is that minimum payoff guaranteed by a maxmin strategy. A conservative agent would prefer the maxmin strategy.

Minmax strategy is a strategy that minimizes other’s worst-case payoff.

Theorem

In any finite, two-player, zero-sum game, in any Nash equilibrium each player receives a payoff that is equal to both his maxmin value and his minmax value.

Note: in non-zero-sum game, Nash equilibrium may not equal to maxmin or minmax strategy.^1

Corrleated Equilibrium

Correlated Equilibrium (informal): a randomized assignment of (potentially correlated) action recommendations to agents, such that nobody wants to deviate.

Reference: Correlated equilibrium^2.

This week’s Game Theory is dedicated to Mixed-Strategy Nash Equilibrium.

Mixed strategy, different from pure strategy, means that players can choose an action according to a specific probability distribution (among all possible actions). The following concepts and definitions all derives from this idea:

Strategy $s_i$

any probability distribution over the actions $A_i$ for agent i.

Pure strategy

only one action is played with positive probability.

Mixed strategy

more than one action is played with positive probability.

Support (of mixed strategy)

all the actions

We denote $s_i \in S_i$ as $S_i$ is the set of all strategies for user i. All strategies $S = S_1 \times S_2 \times \ldots \times S_n$

Expected Utility is defined as follows:

In the equations above, a means a possible action profile from A. $a_j$ does not mean each of the action but the player j’s corresponding action in the corresponding profile.

Best response

$s_{i}^{} \in BR(s_{-i}) iff \forall s_i \in S_i u_{i}(s_{i}^{}, s_{-i}) \ge u_{i}(s_i, s_{-i})$

Nash Equilibrium

$s=<s_1, s_2,=”” \ldots,=”” s_n=””> \mbox( is a Nash Equilibrium iff }\forall i, s_i \in BR(s_{-i})$</s_1,>

Theorem

Every finite game has a Nash Equilibrium. (While comparing to pure strategy games!)

It is often very hard to compute the Nash Equilibrium of a game, but in simple cases, in which we know the support, we can get the Nash Equilibrium by being acknowledged that a player will act indifferently facing a mixed strategy.

This week’s game theory was dedicated to introduction, overview, uses of game theory, some applications and examples, and formal definitions of: the normal form, payoffs, strategies, pure strategy Nash equilibrium, dominant strategies..

Define a Game

1. Normal form: List what payoffs get as a function of their actions.
2. Extensive form: Includes timing of moves, players moves sequentially, represented as a tree.

Finite, n-person normal form game: $<n, a,=”” u=””>$:</n,>

• Players: $N={1, \ldots, n}$, indexed by i;
• Action set for player i: $a=(a_1, \ldots, a_n) \in A = A_1 \times \ldots \times A_n$ is an action profile;
• Utility function or Payoff function for player i: $u_i:A \mapsto \mathbf{R} $, $u=(u_1, \ldots, u_n)$ is a profile of utility functions.

Type of Games

Nash Equilibrium

In game theory, the Nash equilibrium is a solution concept of a non-cooperative game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only their own strategy. If each player has chosen a strategy and no player can benefit by changing strategies while the other players keep theirs unchanged, then the current set of strategy choices and the corresponding payoffs constitute a Nash equilibrium.[^1]

Someone has an incentive to deviate from a profile of actions that do not form an equilibrium.

Best Resopnse
: If you knew what everyone else was going to do, it would be easy to pick your own action.

Nash equilibrium looks for stable action profiles.

Dominant Strategies

Strategy (currently) is choosing an action (“pure strategy”)

Denote $s_i$ and $s_i’$ as two strategies for player i, and $S_{-i}$ be the set of all possible strategy profiles for the other players.

$s_i$ strictly dominates $s_i’$ if $ \forall s_{-i} \in S_{-i}, u_{i}(s_i, s_{-i}) \gt u_{i}(s_i’, s_{-i})$
$s_i$ very weakly dominates $s_i’$ if $ \forall s_{-i} \in S_{-i}, u_{i}(s_i, s_{-i} ) \ge u_{i}(s_i’, s_{-i})$
Please pay attention to the difference between best response, which lies in the definition of strategy.

A strategy profile consisting of dominant strategies for every player must be a Nash equilibrium! An equilibrium in strictly dominant strategies must be unique.

Pareto Optimality

Some times, one outcome $o$ is at least as good for every agent as another outcome $o’$, and there’s some agent who strictly prefers $o$ to $o’$.

An outcome $o^*$ is Pareto-optimal if there is no other outcome that Pareto-dominates it.

[^1]: Nash equilibrium, https://en.wikipedia.org/wiki/Real_number

《算法导论》教导我们，图有两种表达方法：邻接链表和邻接矩阵。至少是对于有环的图来说，的确是这样。对于树和图究竟怎样表达最好，我一直都在摸索之中。以前在写与图有关的算法的时候，总是要把整个邻接链表（通常是一个很大的std::vector<std::list<T>>&）当作参数的一部分送进去。这样看着就很别扭，但是这确实是严格按照《算法导论》的定义实现的。

因此我对我的代码质量深表担忧。但是幸运的是，最近我开始学习起别人的代码，从中获得了一些启示。今天总结的是这么一种特殊的图————自由树的表达方法。这种方法高效，无论是从时间上还是空间上。

假定现在给出一系列树边，每行一条树边记录，由两个数组成。第一个数代表父结点，第二个数代表子结点。这一系列树边可以组成一棵树（或一片森林）。对于这样的信息，利用下面这种方法可以给出高效的表达。

首先我们定义如下结构和数组：

1
2
3
4
5
6
7

typedef struct{
    int v;
    int prev;
}edge_t;

edge_t edges[N]; //边
int head[N];     //结点

我们知道，在一棵结点数为V的树中，一共有V-1条边。因此给结点和边各开V大小的数组是没问题的。利用这样的数据结构，我们使用如下方法读取边：

1
2
3
4

//for each edge (u,v)
edges[i].v=v;
edges[i].prev=head[u];
head[u]=i;

从这段代码中，我们可以看出如下基本事实：

1. edges以边序号为索引，其中v记录的是该边的子结点，prev记录的是另一条边序号；
2. head以结点序号为索引，其中记录的是边序号；
3. 在第一次涉及到父结点u时，head[u]为0，此时将此值赋给prev，代表空边。在这之后，head[u]被赋予本边序号；
4. 如果再次遇到父结点u，head[u]会被新的边序号覆盖。
5. 因此，head实际上存储着以某个结点为父结点时，其在读取顺序中的最后一条边。如果无子结点，则为0.

那么，每个结点最多只存储一条边，如何实现多个子结点的情况？事实上，我们在读到这“最后一条边”时，依照读取顺序的上一条边已经被存储在edges[i].prev中了。按照如下代码，可以方便地完成对某个结点所有子结点的遍历：

1
2
3

for(int k=head[i]; k!=0; k=edges[k].prev){
    //do something
}

这种方法适用于：

• 数据以自由树形式表达；
• 输入数据是边的信息，且标明了父亲孩子关系。
• 输入边的顺序可以任意。如果要确定根结点，只要再加上一个bool isroot[V]就可以在读取的时候把所有子结点标注出来。

求一个自由树的直径。对于直径，《算法导论》第三版 349 页练习 22.2-8 上面这么定义道：

树中所有最短路径的最大值即为树的直径。

这个树由于没有根结点，其实直径这个概念，还是理解为一个连通无向无环图的直径为好。

现在给定如下格式的输入：

8
1 2
1 3
1 4
4 5
3 6
6 7
7 8

第一行是这个图的结点个数，不妨记为 N，以下 N-1 行是 N-1 条边，结点序号按照 1-N 顺序编号。求这个图的直径。

这个输入的输出结果是 6，给出这个示意图就可以看得很清楚：

对于这个问题，最笨的方法就是对每一个结点进行 BFS，因为 BFS 有这个性质：BFS 生成的 广度优先树的每一个结点到达根结点的路径总是最短路。这样，把每一个结点 BFS 一遍就会生成一个该结点到达的最远结点。按照定义取出最长的路径即可。由于 BFS 时间复杂度是 O(N)，这个方法的时间复杂度是$O(N^2)$。

其实还有一个更为简便的方法：首先对任意一个结点做 BFS 求出最远的结点，然后以这个结点为根结点再做 BFS 到达另一个最远结点。第一次 BFS 到达的结点可以证明一定是这个图的直径的一端，第二次 BFS 就会达到另一端。下面来证明这个定理。

但是在证明定义之前，先证明一个引理：

引理：在一个连通无向无环图中，x、y 和 z 是三个不同的结点。当 x 到 y 的最短路与 y 到 z 的最短路不重合时，x 到 z 的最短路就是这两条最短路的拼接。

证明：假设 x 到 z 有一条不经过 y 的更短路$\delta (x,z)$，则该路与$\delta (x,y)$、$\delta (y,z)$形成一个环，与前提矛盾。

定理：在一个连通无向无环图中，以任意结点出发所能到达的最远结点，一定是该图直径的端点之一。

证明：假设这条直径是$\delta (s,t)$。分两种情况：

1. 当出发结点 y 在$\delta (s,t)$时，假设到达的最远结点 z 不是 s,t 中的任一个。这时将$\delta (y,z)$与不与之重合的$\delta (y,s)$拼接（也可以假设不与之重合的是直径的另一个方向），可以得到一条更长的直径，与前提矛盾。
2. 当出发结点 y 不在$\delta (s,t)$上时，分两种情况：

1). 当 y 到达的最远结点 z 横穿$\delta (s,t)$时，记与之相交的结点为 x。此时有$\delta (y,z)=\delta (y,x)+\delta (x,z)$。而此时$\delta (y,z)>\delta (y,t)$，故可得$\delta (x,z)>\delta (x,t)$。由1的结论可知该假设不成立。

 2). 当 y 到达的最远结点 z 与$\delta (s,t)$不相交时，记 y 到 t 的最短路首先与$\delta (s,t)$相交的结点是 x。由假设$\delta (y,z)>\delta (y,x)+\delta (x,t)$。而$\delta (y,z)+\delta (y,x)+\delta (x,s)$又可以形成$\delta (z,s)$，而$\delta (z,s)>\delta (x,s)+\delta (x,t)+2\delta (y,x)=\delta (s,t)+2\delta(y,x)$，显然与题意矛盾。

因此定理成立。

9月21日补充：这道题是上一周 hihocoder 上面的一道题。出题者的原意并不是要我们这么做。出题者写了很长的一段提示，但是这段提示的语文表述很差，完全没有抓住重点，导致我花了一个星期的时间也没弄明白他在讲什么。现在所有人的源代码均已公开，可以继续下去了。

出题者的原意是要我们使用这么一个定理：

定理2：树的直径，等于以树直径上任意一点为根的有根树，其左子树的高度+1，再加上其右子树高度+1。

按照这种定理的定义，我们可以设计这样一个程序，对每个结点计算左子树高度+右子树高度+2.这样的时间复杂度是$O(n^2)$。由于我们不知道所选取的结点是否是在直径上，所以要进行这样的枚举。显然这会超时。但是根据本文的提示，寻找这种直径的过程其实可以递归化：

1. 在根结点的左子树上；
2. 在根结点的右子树上；
3. 直径经过根结点。

于是我们可以设计这样的程序：选取任意结点为根结点，递归地计算每个结点的高度。在结点内部计算高度的同时，计算以当前结点为根的子树的左子树高度+右子树高度+2，用于更新全局树直径。

对我来说，对随机事件的分析，恐怕是最难的。我原以为我数学学得还可以，直到我遇上了随机过程。这篇 blog 所讲的是算法分析，其中涉及到大量对随机情况的分析。因此我在此将其梳理一下，特别注重挖掘不同算法之间的分析过程的相似性。

快速排序是一种原址排序方法，随机化的快排具有 O(nlgn) 的期望运行时间。这个在《算法导论》（第三版）的 7.4.2 节中有一个以比较操作为中心的证明方法。这个证明的核心思想就是：快速排序是由多次 partition 过程组成的，因此关键问题就在于获得 partition 过程的运行时间和运行 partition 过程的次数。partition 过程的最大运行次数是 n-1 次，可以记为 O(n) ，对于其运行时间，练习 7.1-3 给出的结论是 Θ(n) 。这样乍一算，似乎是 O($n^2$) 的时间复杂度。这样计算是错误的，因为 partition 的时间复杂度与其长度有关。这里，我们需要更为细致的分析。决定 partition 运行时间的是其内部循环次数。这个循环次数可以统计每次必须运行的比较次数而得到。通过计算整个 quicksort 的比较次数，我们就可以得到真正的 partition 循环次数。而这个比较次数的期望值，可以通过拆分成示性随机变量相加得到。这个分析的精华之处就在于分析出每两个元素进行比较的概率。很有意思，可以进行比较的组合是 Θ($n^2$) ，但是最终全部比较次数的期望是 O(n lgn) 。

当然这个只是作为复习，不是今天的重点。这个方法实在是太不直观了点。这次我们用类似于 merge-sort 的分析方法进行分析。

快速排序分析

按照 merge-sort 的分析思路，quicksort 是将一个问题拆分成了两个子问题，但是由于子问题大小不是固定的，这时候就只能分析运行时间的期望。随机化的快速排序使得任何一个元素成为主元都是等可能的。因此我们有如下式子：

随后，可以通过代入法，把 n lgn 代入 T(n)。其中，有如下不等式可以利用：

由于这个不等式的天赐特性，我们只能记住，有如（1）式的结论就是 O(n lgn) 。

二叉搜索树分析

我们知道，二叉搜索树的动态操作时间复杂度是 O(h) 。但是对于随机构建的二叉搜索树来说，其期望树高是 O(n lgn) ，对于随机构建的二叉搜索树来说。这里我们证明的是一个稍弱于此定理的定理：**随机构建的二叉搜索树的平均节点深度为 O(n lgn)**。

为表示每一个节点的深度，我们记树**T**的节点x的深度为 d(x, T) ，而全部节点的深度之和记为 P(T) 。节点平均深度可以表示为

而每一棵树可以拆分为节点与左子树、右子树。我们需要注意，当把 P(T) 拆分为$P(T_{left})$和$P(T_{right})$之后深度还应该增加当前树总节点再减一。也就是

对于某一棵树确实是这样。但是这棵树是随机构建的。如何表示出 P(T) 的期望值？事实上，这里和快速排序一样，在随机构建的过程中，第一个元素总是根节点，每一个元素成为第一个元素的概率都是相等的。因此，我们可以据此写出：

其中 P(n) 是具有 n 个节点的树高。这时候，我们发现，这和在快速排序那里推导出来的式子是非常相似的。因此，延续着快排分析的思路，可以分析出 P(n) = O(n lgn)。

知道这一点有什么用呢？当构建一棵二叉搜索树时，第一个元素会被选为根节点，其后的元素，每一个都要和其比较。这和快速排序的比较次数是一样的。因为当一个元素选为主元的时候，其后的每一个元素都要和其比较。这样，当用相同的序列构建二叉搜索树和进行快速排序的时候，他们所需要的比较次数是相同的。

关于XML的文章我先前写过一篇。之后就再也没写过。原因是很简单的。虽然那篇文章是用Matlab的代码说明XML解析，但是XML的基本概念都是一致的，我也没必要再就C++或是Python等语言再写一遍在其他语言下面怎么用其他的库解析XML，都是大同小异。

可是这个世界上奇葩比较多。最近在做《网络通信原理》的project的时候，用到了Qt里面的QXmlStreamReader。有意思的是，这个东西不按常理出牌。为说明这个特性，我引用Qt 5关于QXmlStreamReader上面的一段话：

QXmlStreamReader is an incremental parser. It can handle the case where the document can’t be parsed all at once because it arrives in chunks (e.g. from multiple files, or over a network connection).
…
QXmlStreamReader is memory-conservative by design, since it doesn’t store the entire XML document tree in memory, but only the current token at the time it is reported.

由这段话我们可以看出，QXmlStreamReader的一个重要特点是，它是一个增量parser。QXmlStreamReader有一个特别的构造函数QXmlStreamReader::QXmlStreamReader(QIODevice * device)，这个device可以是QNetworkReply也可以是QFile。相信这样的好处大家都可以看得出来。为了应付不同IODevice的特性，QXmlStreamReader也只能采取增量解析的方法。然后又有了下面的概念：token.

QXmlStreamReader不在内存中保存全部的DOM tree，现在解析的位置和所解析的对象用token说明。关于什么是token，其实我也不知道。但是QXmlStreamReader提供了一个函数：TokenType QXmlStreamReader::readNext()，有关这个函数的说明是“Reads the next token and returns its type.”

按照官方文档上面的解释，一个可行的解析模型可以是这样：

1
2
3
4
5
6
7
8
9

QXmlStreamReader xml;
...
while (!xml.atEnd()) {
      xml.readNext();
      ... // do processing
}
if (xml.hasError()) {
      ... // do error handling
}

由此可见，QXmlStreamReader在解析xml的时候，以token为单位解析xml文档数据。

我在上一篇文章中讲过，xml有Element node，Element node以Text node作为child，Attribute node从属于Element node，comment node相对独立，而以上四种node都由document node生成，document node可以说是一个xml文档的代表，xml parsing的核心是element node。但是在Qt中，token与这种标准的概念似乎完全无关。它更关心我现在读到的东西是什么。在TokenType的定义中，一共给出了9种不同token的定义，而判断当前parser的tokenType是什么的函数一共有十二种。

我们可以想象，这种parser，一块一块地读取xml文档，只前进不后退，每一块代表一种既定的token，直到全部读完xml为止（也就是atEnd()为真的时候）。

下面让我展示一段我这个project中的一段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

if(reply->error()==QNetworkReply::NoError){
    ui->listWidget->clear();
    articlelist.clear();
    QXmlStreamReader xml(reply);
    if(xml.readNextStartElement() && xml.name()=="articles"){
        while(xml.readNextStartElement() && xml.name()=="article"){
            Article record;
            while(xml.readNextStartElement()){
                if(xml.name()=="author"){
                    record.author = xml.readElementText();
                }else if(xml.name()=="date"){
                    record.date = xml.readElementText();
                }else if(xml.name()=="title"){
                    QString t = xml.readElementText();
                    ui->listWidget->addItem(t);
                    record.title = t;
                }else if(xml.name()=="content"){
                    record.content = xml.readElementText();
                }
            }
            articlelist.push_back(record);
        }
    }
    ...
}

xml文档格式如下：

1
2
3
4
5
6
7
8
9
10
11
12

<articles>
  <article>
    <author>...</author>
      <date>...</date>
    <title>...</title>
    <content>...</content>
  </article>
  <article>
  ...
  </article>
  ...
</articles>

代码中reply是个API请求的回应，我的目的是吧这个回应中的每一条信息存放在articlelist中。值得注意的是14-16行那段代码，由于这个是一个增量parser，我们不能使用

1
2

ui->listWidget->addItem(xml.readElementText());
record.title = xml.readElementText();

否则record.title将为空。