You tell me I'm wrong. Then you'd better prove you're right.

2015-01-17
Misha and Permutations Summation

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

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

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

排列 字典序大小
012 0
021 1
102 2
120 3
201 4
210 5

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

$$\begin{aligned} 42 &amp; = 1 \times 4! + 3 \times 3! + 0 \times 2! + 0 \times 1! + 0 \times 0! \\   &amp; = (((1 \times 4 + 3) \times 3 + 0) \times 2 + 0) \times 1 + 0 \\   &amp; = 13000_{!} \end{aligned}$$

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

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

排列 阶乘数系 字典序大小
012 000 0
021 010 1
102 100 2
120 110 3
201 200 4
210 210 5

  那么在阶乘系统下表示出来的数字,好像和排列没有明显的联系啊。好像还不如用原始的方法,就是直接从排列计算出字典序大小呢。那么这一过程怎么计算呢,用最原始的思路?比如说我们现在有排列 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 的整数次方相关联的树状组织。

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

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

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

  总结:

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

2015-01-03
OJ 总结(Depricated)

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。其实可以从每个数组尾端开始,从大到小插入。但是这样会不会污染原有数据呢?用数学方法证明一下即可。

2014-11-01
Game Theory Note - week 3

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

Prisoner 1 and 2 Co Be
Co -0.5, -0.5 -10, 0
Be 0, -10 -2, -2

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.

Small pig and big pig Press Wait
Press 1,5 -1,9
Wait 4,4 0,0

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.

2014-10-18
Game Theory Note - week 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:
$$\begin{equation} u_{i}(s) = \sum_{a \in A} u_{i}(a) P(a|s) \ P(a|s) = \prod_{j \in N} s_j(a_j) \end{equation}$$
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=\ \mbox( is a Nash Equilibrium iff }\forall i, s_i \in BR(s_{-i})$

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.

2014-10-12
Game Theory Note - week 1

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: $$:

  • 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

Type of Game Properties Examples
Pure Competition 1. Exactly two players of opposed interests; Zero sum special case when $u_1(a)+u_2(a)=0$ Matching Pennies, Rock-Paper-Scissors
Coordination Players have same interests: $\forall a \in A, \forall i,j, u_i(a)=u_j(a)$ side of road
Coordination and Competition Battle of the Sexes

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

2014-10-04
一种树的表达法

《算法导论》教导我们,图有两种表达方法:邻接链表和邻接矩阵。至少是对于有环的图来说,的确是这样。对于树和图究竟怎样表达最好,我一直都在摸索之中。以前在写与图有关的算法的时候,总是要把整个邻接链表(通常是一个很大的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]就可以在读取的时候把所有子结点标注出来。

2014-09-21
树的直径

求一个自由树的直径。对于直径,《算法导论》第三版 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,用于更新全局树直径。

2014-07-27
二叉搜索树与快速排序的内在相似性

对我来说,对随机事件的分析,恐怕是最难的。我原以为我数学学得还可以,直到我遇上了随机过程。这篇 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 是将一个问题拆分成了两个子问题,但是由于子问题大小不是固定的,这时候就只能分析运行时间的期望。随机化的快速排序使得任何一个元素成为主元都是等可能的。因此我们有如下式子:

$$\begin{aligned} E[T(n)] & = E \left[ \sum^{n}_{q=1} X_q \left( T(q-1) + T(n-q) + \Theta (n) \right) \right] \\ & = \frac{2}{n} \sum^{n-1}_{q=2} E[T(q)] + \Theta (n) \end{aligned}$$

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

$$\begin{equation} \sum^{n-1}_{k=2} k \log k \le \frac{1}{2} n^2 \log n - \frac{1}{8} n^2 \end{equation}$$

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

二叉搜索树分析

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

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

$$\begin{equation} \frac{1}{n} \sum_{x \in T} d(x, T) = \frac{1}{n} P(T) \end{equation}$$

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

$$\begin{equation} P(T)=P(T_{left})+P(T_{right})+n-1 \end{equation}$$

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

$$\begin{equation} E[P(n)]=E\left[ \frac{1}{n} \sum_{k=0}^{n-1}(P(k)+P(n-k-1)+n-1)\right] \end{equation}$$

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

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

2014-05-30
简单易懂的XML parsing——Qt篇

关于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将为空。

2014-03-11
简单易懂的XML parsing

读取一个XML文件,返回一个DOM对象。

什么是DOM对象?全称为Document Object Model, XML文件中的每一个东西都对应为一个node。DOM node的属性和方法遵循国际互联网的标准。

有以下类型的nodes:

  • Element nodes* Text nodes 每一个Text node都是Element node的child
  • Attribute nodes 不是任何node的parent 或 child,从属于element node
  • Comment nodes* Document nodes 只有使用document node的方法才能创造新element, text, attribute, comment

现有以下xml文档:

1
2
3
4
5
6
7
8
9
<listitem>
<label>Import Wizard</label>
<callback>uiimport</callback>
<icon>ApplicationIcon.GENERIC_GUI</icon>
</listitem>
<listitem>
...
</listitem>
...

其中的一个label标签有字符Plot Tools。假设你想在同样的listitem里面寻找callback标签的字符:

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
26
27
28
29
30
findLabel = 'Plot Tools';
findCbk = '';
xDoc = xmlread(fullfile(matlabroot, ...
'toolbox','matlab','general','info.xml'));
allListitems = xDoc.getElementsByTagName('listitem');
for k = 0:allListitems.getLength-1
thisListitem = allListitems.item(k);
% Get the label element. In this file, each
% listitem contains only one label.
thisList = thisListitem.getElementsByTagName('label');
thisElement = thisList.item(0);
% Check whether this is the label you want.
% The text is in the first child node.
if strcmp(thisElement.getFirstChild.getData, findLabel)
thisList = thisListitem.getElementsByTagName('callback');
thisElement = thisList.item(0);
findCbk = char(thisElement.getFirstChild.getData);
break;
end
end
if ~isempty(findCbk)
msg = sprintf('Item "%s" has a callback of "%s."',...
findLabel, findCbk);
else
msg = sprintf('Did not find the "%s" item.', findLabel);
end
disp(msg);

MATLAB本身就提供一个xmlread函数,其返回的是Document Node。根节点哦。其余与Document Node的函数都是标准已经定义了的,这个标准详情请见这里.在上面一段代码中,我们可以看见几个常用的API:

  • getElementsByTagName是Document Node的方法,返回一个list。
  • 这个list是node的列表,要得到其中一个元素,需要调用list的item方法。
  • 一个有child的element node,获得其内容,要调用getFirstChild.getData

如果我们想写一个XML文档:

1
2
3
4
5
6
7
8
9
<?xml version="1.0" encoding="utf-8"?>
<toc version="2.0">
<tocitem target="upslope_product_page.html">Upslope Area Toolbox<!-- Functions -->
<tocitem target="demFlow_help.html">demFlow</tocitem>
<tocitem target="facetFlow_help.html">facetFlow</tocitem>
<tocitem target="flowMatrix_help.html">flowMatrix</tocitem>
<tocitem target="pixelFlow_help.html">pixelFlow</tocitem>
</tocitem>
</toc>

MATLAB代码如下:

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
26
docNode = com.mathworks.xml.XMLUtils.createDocument('toc');
toc = docNode.getDocumentElement;
toc.setAttribute('version','2.0');
product = docNode.createElement('tocitem');
product.setAttribute('target','upslope_product_page.html');
product.appendChild(docNode.createTextNode('Upslope Area Toolbox'));
toc.appendChild(product)
product.appendChild(docNode.createComment(' Functions '));
functions = {'demFlow','facetFlow','flowMatrix','pixelFlow'};
for idx = 1:numel(functions)
curr_node = docNode.createElement('tocitem');
curr_file = [functions{idx} '_help.html'];
curr_node.setAttribute('target',curr_file);
% Child text is the function name.
curr_node.appendChild(docNode.createTextNode(functions{idx}));
product.appendChild(curr_node);
end
xmlwrite('info.xml',docNode);
type('info.xml');
  • 这个函数首先先创建出一个Document Node,也就是最重要的根节点;
  • SetAttribute是Element Node的方法;
  • element, text, attribute, comment只能由docNode创建,方法是createXXXNode
  • Element Node间的父子关系由appendChild确定。

以上就是MATLAB里面处理XML文档的最基本知识。由于XML文档的处理方式是统一的,因此很容易就能拓展到其他语言。从代码中就可以挖掘出许多东西。在实际中,要使用到的XML API恐怕还远远不够。这篇文章只是作为一个入门性质的导引。