归并排序是一种相当稳健的排序算法，无论何种输入序列，其期望时间复杂度和最坏时间复杂度都是Θ(nlogn),这已经达到了基于比较排序算法的渐进下界。

因此归并排序时常会用于对可能导致quicksort退化的序列排序。

归并排序是典型的分治算法，一个最常见的实现如下：

void MergeSort(int a[], int low, int high)
{
	if (low < high)
	{
		int midIndex = (low + high) >> 1;
		// take apart
		MergeSort(a, low, midIndex);
		MergeSort(a, midIndex + 1, high);

		Merge(a, low, midIndex + 1, high);
	}
}

void Merge(int a[], int lowFirst, int highFirst, int highLast)
{
	int l = lowFirst;
	int r = highFirst;
	int len = highLast - lowFirst + 1;

	int* pBuffer = new int[len];
	_ASSERT(pBuffer != NULL);
	int* p = pBuffer;

	while (l < highFirst && r <= highLast)
	{
		*p++ = (a[l] <= a[r]) ? a[l++] : a[r++];
	}

	while (l < highFirst)
	{
		*p++ = a[l++];
	}

	while (r <= highLast)
	{
		*p++ = a[r++];
	}   

	p = pBuffer;
	for (int i = lowFirst; i <= highLast;)
	{
		a[i++] = *p++;
	}

	delete [] pBuffer;
}

但是在实践中，归并排序花费的时间往往超过预期，对于普通的序列而言，所花费的时间甚至远远超过quicksort。

究其原因，和归并排序的内存策略有关。

归并排序不是原地排序，需要额外的存储空间。并且在每次Merge过程中，需要动态分配一块内存以完成对两个数据堆的排序合并。并且排序完毕之后，我们需要将存储空间中的数据复制并覆盖原序列。

最后一步操作是由归并排序自身性质决定，无法优化，所以我们只能针对Merge操作。

经过分析很容易知道，对于长度为n的序列，要执行logn次的merge操作，这意味着需要进行logn次的内存分配和回收。内存操作开销较大。
Read the rest of this entry »

又是一周发文时。。。这次写篇槽文好了

题目来自上届的信息技术应用大赛复赛题，题目描述如下：

用1，2，3组成长度为n的字符串，要求相邻的子串不能重复。输出所有合法的字符串

和ACM之类的比赛不同，这比赛的题目对于算法居然没有时间要求，估计为了降低参赛门槛吧。

既然没有时间限制，只要想一个正确的算法就行，懒得管他复杂度多奇葩。

最容易想到的一个算法是,每生成一位数字后进行有效性测试,符合的话继续探测。而有效性测试的算法也可以有很多种。

最直接的是从末位往前检测，依次比较相邻的字串是否重复。对于长度为k的串而言，最多比较（指的是重复性）[k/2]次。

这种算法的复杂度应该在O(n^3)。

前天晚上当我洗澡回来时，郁磊刚好给出了这个算法的实现。不过代码木有了- -

而在洗澡时，我恰好想到了一种比较奇葩的解法。此方法和Programming Pearls中求解最大子向量和的递归解法相似。

对于长度为k的字符串，首先分成p1=floor{k/2}和p=2ceiling{k/2}两部分，从中间开始往两边遍历检测。如果检测合法，即说明p1和p2中相邻的字串必定不重复。

接着再同时递归处理两部分，停止条件为最后划分出来的集合只有一个元素。

最初郁磊认为这道题和书中的题目并不类似，这个算法应该不能用。但是我一直认为两个题目的模型类似，算法可行。遂花了大约一刻钟，写出了实现代码。

感谢郭嘉，这算法在不考虑性能的情况下运行良好。

有效性检测的代码如下：

bool CheckStr(wchar_t* sz, int low, int upper)
{
	if (low == upper)
	{
		return true;
	}

	int leftEnd = (low + upper) >> 1;
	int rightStart = leftEnd + 1;

	for (int i = 0; leftEnd - i >= low && rightStart + i <= upper; ++i)
	{
		if (!wcsncmp(&sz[leftEnd-i], &sz[rightStart], i + 1))
		{
			return false;
		}
	}

	bool l = CheckStr(sz, low, leftEnd);
	bool r = CheckStr(sz, rightStart, upper);

	return l && r ? true : false;
}

由于这里的递归为分治策略，所以复杂度分析要稍微复杂些。

我们首先可以确定当串长度为n时整个递归表达式为

T(n) = 2T(n/2) + f(n)

这里的f(n)为中间往两边检测的复杂度，经过分析可以得到

f(n) = sigma(1,[k/2]) = O(n^2)

带入得到递归表达式

T(n) = 2T(n/2) + O(n^2)

根据主定理分析，上述表达式属于第三种情况：n^logb(a)小于f(n)且多项式小于，且存在小于1的正数c使得

af(n/b) <= cf(n)

成立（这里取c=1/4即可）

所以递归式的复杂度是O(n^2)，而由于这是生成一个测试位的复杂度，所以整体复杂度为O(n^3)

这里提下生成过程，经过优化的最多测试次数为2(n-1)

虽然无论是直接的反向检测还是递归分治，复杂度都并不好看，但是经过实际测试，发现当n比较大时，符合条件的数反而更少。

另外，以上讨论的方法都是基于生成测试法。似乎此算法的下界也至少是立方复杂度（未证明）。

所以如果要设计更高效的算法的话，应该需要换一个角度。

表达式树是树结构的一个经典应用，常用于编译器的设计。

在表达式树中，叶子通常是常数值或者变量名，统称为操作数（operands）。而其他非叶子结点则包含各种操作符（operators）。

在不同的词法解析中，表达式树的分支设计也不同。对于简单的诸如表达式求解而言，表达式树往往采用二叉树。这是因为每一个操作符正好对应两个操作数。

而在包含一元操作符（e.g自增自减操作符）或三元操作符的复杂情况下，每个操作符结点拥有的不再是两个孩子结点，此时二叉树便显得不太适用。

在此处的简单实现，我们只考虑适合二叉树的表达式求解，其余情况请自行翻阅编译原理相关书籍。当然，无论是哪种情况，本质的算法思想是相同的。

0.构造表达式树

要构造一个表达式树，首先要将一般的中缀表达式（infix）转换成逆波兰式（即后缀表达式，postfix）。

PS：关于逆波兰式以及infix和postfix的转换，请参考我之前的一篇文章http://blog.kingsamchen.com/archives/637

对于中缀表达式(a+b)*(c*(d+e))，其逆波兰式为ab+cde+**，我们现在结合这个表达式，阐述利用逆波兰式构造表达式树的一般步骤。

在构建表达式树时，我们需要一个堆栈，用于保存树或者结点的指针，记这个堆栈为S。

我们对逆波兰式进行遍历，如果碰到的是

（1）操作数，那么则建立一个叶子结点，数据为操作数，并将结点指针保存到堆栈中
（2）操作符，那么从堆栈中弹出两个指针，分别为p2和p1.建立一个结点，内容为操作符，然后分别将结点的左右孩子设置为p1和p2，最后将结点指针压入栈

一直重复以上步骤即可。最后堆栈中保存的即是表达式树的根结点指针。
Read the rest of this entry »