珍爱生命，远离政治。我们继续讨论算法。
2008/04/01补充：此算法有重大缺陷。详情请见留言部分。
一年前，我们讨论过一个算法问题，perfect shuffle，据称是个微软面试题：
输入，如何用的时间，的空间，将这个序列顺序改为。

那一次讨论我们翻出了问题的来源，一篇长达12页的论文Computing the Cycles in the Perfect Shuffle Permutation，算法那是非常的复杂，我估...

Xie Xie给我看了一个链接性能调优--永远超乎想象，里面提到了素数筛法的复杂度，作者用实验发现此筛法是线形的。
所谓素数筛法就是那个求小于n的所有素数最简单的算法：
bool* prime(int n) {
bool *p = new bool[n];
memset(p, 0, sizeof p);
for (int i = 2; i < n; i++)
if (!p[i])
for (int j = 2*i; j < n; j+=i)
p[j] = true;
[...]

Rob Pike, 最伟大的 C 语言大师之一 , 在Notes on C Programming(英文原文)中从另一个稍微不同的角度表述了 Unix 的哲学:

你无法断定程序会在什么地方耗费运行时间。瓶颈经常出现在想不到的地方，所以别急于胡乱找个地方改代码，除非你已经证实那儿就是瓶颈所在。
估量。在你没对代码进行估量，特别是没找到最耗时的那部分之前，别去优化速度。
花哨的算法在 n ...

更新：证明的关键一步发现错误，作者更新了论文，结论甚至论文标题都改了（废话），新版本On the graph isomorphism problem。
提交论文到arxiv不需要审阅，一般人都可以提交，所以常有些错误的论文甚至民科作品（在物理和数学领域更多一点）。号称解决图同构问题甚至p vs np以前也有过，不过这次文章的作者的publication记录不错，有2篇ann. of Math.，数量也不少，所以大家稍...

今天香港中文大学的Prof. Cai给我们上graph algorithm。第一节课上教我们玩魔方，先给每人发了一个。我喜欢这样的教学方法 。
魔方的解法，在网上已经有无数了，基本上的思路都是几个定式，玩的时候记住这些定式即可。课上Cai给我们演示了一个他自创的定式，很可惜，我目前为止只学会弄出一面来。
OK，这篇文章的主要目的是讲魔方里的数学，对魔方的群结构研...

一个面试题，号称是微软的
输入，如何在O(n)的时间，用O(1)的空间，将这个序列顺序改为。

刚一眼看上去觉得很容易，做了一回儿才发现深不可测。题目大致是要求在线性时间，常数空间实现下面的置换
x -> 2x mod 2n+1

我做了两小时没做出来，上网一搜，最近这个题目很热，已经有人在讨论这个题目，还翻出了问题的发源地http://www.cs.uvic.ca/~jellis/perfect.ht...

下面是wikipedia上算法的定义：
算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，经过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数据。
算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间...