上次我们谈到，我们考虑时间复杂度时往往假设任意大的整数运算（赋值、四则运算、取余运算、比较运算、位运算包括左移右移）都可以在常数时间内完成，殊不知这留下了一个非常具有研究价值的漏洞：能否利用计算机理想模型中的整数运算，把问题打包成超大整数后并行计算，从而办到一些在普通计算机上无法办到的事情？我们在上一次的文章中介绍了利用“大整数随便算”的漏洞“耍赖”得到了一个线性时间的排序算法。这个漏洞真的已经被充分利用了吗？我们还能从里面榨出多少汁水来？令人无法想象的是，线性时间的排序算法远远没有挖掘到理想大整数运算的巨大潜力，事实上我们能做到常数时间的排序！问题和解答仍然来自Using your Head is Permitted，在这里向Michael Brand表示深深的膜拜。
自然，说“常数时间排序”是有前提条件的，否则即使读入输出也得耗费线性的时间。不过，我们可以假设所有待排序的数都已经打包进一个大整数里，输出时也无需解包，直接返回另一个大整数即可。在这样的情况下，我们完全可以用常数时间完成排序。换句话说，我可以用O(1)的时间，“一下子”就把0100 0111 0001 0010变成0001 0010 0100 0111，不管这个大整数里面装了多少个数。为了方便大家阅读和思考，我们再取一些名字，方便描述。我们把由多个数构成的大整数叫做“整数串”。整数串中所含的数都是二进制，它们用空格隔开。整数串中每个数的位数都必须相等，位数不够用零补足。我们把这个位数叫做“定宽”，本文例子的定宽都是4。
趣题
趣题：扫雷定理 互补棋盘上的数字和相等
这是一个与扫雷游戏有关的非常好玩的问题。给定一个扫雷布局，定义它的“补集棋盘”为这样一个新布局，原来有雷的地方现在是空地，原来没有雷的地方现在都是雷。在棋盘的每块空地上都标有一个数字，它表示周围的8个方块中有多少颗雷。一个美妙的结论是，两个互补棋盘布局上的数字和是相等的。乍看之下似乎不可思议，但仔细一想便豁然开朗。你能想到这是为什么吗？
再谈稠密性：令人吃惊的稠密集及其交集
对于数轴上的一个点集，如果说在集合中任意两点之间都能够找到该集合中的另一个点，我们就说该点集处处稠密。例如，全体有理数集合就是稠密的，任意接近的两个有理数之间都存在其它的有理数（比如它们的算术平均值）。这样看来，两个处处稠密的点集似乎是不能共存的，但实际情况并非如此。我们将会看到越来越牛B的例子，它们将让我们对稠密性有一个全新的认识。
1. 在数轴上找出两个处处稠密的点集，它们互不相交。
很简单。全体有理数和全体无理数就是满足条件的两个集合。
2. 在数轴上找出两个处处稠密的不可数点集，它们互不相交。
很狡猾。集合A取全体正有理数和全体负无理数的并集，集合B取全体正无理数和全体负有理数的并集，这两个集合即可满足条件。
3. 在数轴上找出无穷多个处处稠密的点集，它们两两不相交。
令P_i表示第i个素数。则集合S_i := { √P_i + r| r为有理数 }满足条件。为了证明它们两两不相交，假设r_1 + √P_m = r_2 + √P_n，于是(r_1 – r_2)^2 = (√P_n – √P_m)^2，可得√P_m * P_n = ( P_m + P_n – ((r_1 – r_2)^2) )/2。两个素数的乘积的平方根是一个有理数，这显然是荒谬的（很多证明根号2是无理数的方法都可以证实这一点，例如这里的证法http://www.matrix67.com/blog/archives/206）。
趣题：构造无穷长的字符串序列使每一项都不包含它前面的项
如果删除字符串A中的若干字母可以得到字符串B，我们就说A包含B（熟悉相关概念的网友可能知道，有一个准确的说法叫做“B是A的子序列”，但为了避免和后面的“序列”混淆，我们不用这种说法）。例如，字符串“matrix”包含了“mix”，也包含“ati”，但不包含“it”。字符串序列aaaaa, ab, bbaa, baaaa, aa, bbacc, cbcacc, bb中的每个字符串都不包含它前面的任何一个字符串，我们称这样的字符串序列为“非生成序列”（我自己取的名字，意思是说任一字符串都不能由前面的项通过添加字母生成出来）。我们可以构造出任意长的非生成序列，例如字符串长度严格递减的序列，或者所有不同的长度为n的字符串。现在的问题是，你能构造出一个无穷长的非生成序列吗？当然，你不能使用无穷多种字母来达到这一点。
平面上处处稠密但在平行于坐标轴的直线上无处稠密的点集
我一直很喜欢有各种惊异性质的奇怪函数，比如阶梯状的连续函数、只在一点连续的函数、任意小的区间所对应的值域都是整个实数域的函数等等。在这里面，最令人吃惊的是恐怕要数在平面上处处稠密的单值函数（其实前面那个函数显然也有这样的性质）。这样的函数打破了一维和二维之间的界线，启发人们重新思考稠密性的意义。不过，有人提到，这两个函数之所以在平面上稠密，是因为它们在平行于x轴的直线上都是稠密的。我们自然开始设想，有不有可能在平面上找到这样一个点集，它在平面上处处稠密，但在任意一条平行于坐标轴的直线上都无处稠密呢？
这是可以办到的。为了简便起见，我们只考虑平面区域[0,1]×[0,1]上的点集。让我们考虑由所有满足以下条件的点(x,y)所组成的点集：x和y都是有限小数，并且小数位数是相同的。例如，点(0.0516, 0.1025)就属于这个点集，但(0.23, 0.1001)就不属于这个点集，(1/3, π/6)就更不属于该点集了。显然，对于任何一个有限小数x’，直线x=x’上都只有有限多个点；类似地，对于任意一个有限小数y’，直线y=y’上都只有有限多个点。因此，该点集在所有平行于坐标轴的直线上都无处稠密。有趣的是，该点集在整个平面区域内却处处稠密。在任意小的区间x’-ε≤x≤x’+ε，y’-ε≤y≤y’+ε中，总存在一对小数位数相同的x和y。我们只需要写出一个比ε更小的有限小数λ，然后取(x’+λ, y’+λ)（只保留和λ相同的位数），则该点必然在前面所说的范围内。