趣题:理想模型下的排序算法(上)

    当我们研究复杂度时,我们往往会将现实机器进行理想化。例如,我们说冒泡排序是O(n^2)的,这其实是不准确的。这个论断假设整数之间的比较运算是O(1)的,而事实上它们是O(log(min(|a|,|b|)))的。多数时候我们都认为这种机器模型的理想化是合理的,毕竟这让问题简化了不少,并且也能反映出算法的本质。但大家有想过吗,这个“大整数随便算”的假设其实是一个超级大漏洞,我们可以利用理想模型中的这一漏洞来作弊,获得时间复杂度更低的算法。上个月,Michael Brand在他的UyHiP里就提出了这样一个问题:假设计算机对任意大整数的赋值、四则运算、取余运算、比较运算、位运算(包括左移右移)的复杂度都是常数级别,你能否设计出一个O(n)的排序算法来?

    我非常喜欢这个题目。月初的时候我就提交了一个正确的算法。我们将用左移和加法运算把整数序列编码成一个超大整数,然后利用排序网络进行并行排序。这个算法比较复杂,你可以按照下面的思路一步一步得到这个算法。

1. 如何用位运算来取绝对值

2. 给出两个正整数a, b,不用比较运算和判断语句如何把小数赋给a,大数赋给b?
    提示:和加差除以2等于大数,和减差除以2等于小数

3. 如何利用位运算把整数序列编码成一个超大整数?
    例如把(二进制数)11, 1011, 1110, 1编码为一个数00011 01011 01110 00001

4. 如何用位运算给超大整数中的所有数同时取绝对值?

5. 给出两个超大整数a, b,不用比较运算和判断语句如何把对应位置上的小数赋给a的对应位置,大数赋给b的对应位置? 例如把
      a = 000010 000111 000100 001001
      b = 000001 001011 000011 011111
    变成
      a = 000001 000111 000011 001001
      b = 000010 001011 000100 011111

6. 如何实现奇偶移项排序

    最后,由于奇偶移项排序只有O(n)层,因此整个算法是O(n)的。

    但是,这个算法太繁琐了,不具有美观性。虽然这个算法是我自己想出来的,但我仍然很不满意。待我看了这个月Michael Brand发布的答案后,我一拍大腿,哎呀,还有一个如此简单巧妙的算法我没想到!相比之下,我的算法太复杂了,原因就在于我还没有充分挖掘到“大整数的常数级运算”的潜力。这个理想模型的假设太强大了。打开思路,放宽思维,大胆想象,从更大的尺度上来思考,我们可以得到一个简单得出奇的线性排序算法来。


    这个理想模型牛B就牛B在,我可以用大整数实现任意长度的数组的常数级别存取!比如,我们假设数组a的“单位宽度”为w,那么让a[i]自加一就相当于让一个超大二进制整数a加上1<<(i*w)。想要取出a[i]的值,也就相当于让a>>(i*w)再模1<<w。再回想位运算的一个妙用:x and (x xor (x-1)),或者写成x and -x,可以取出(二进制数)x的最右边那个1。此时,问题立刻迎刃而解。维护一个超级超级长的二进制数a,再维护一个超级超级长的数组b。只要读到一个数x,如果b[1<<x]为0,我们就让a加上1<<x。然后,令b[1<<x]自加一。输出时,只需要不断取a中位置最低的那个“1”,然后按照b数组的值输出相应多个数即可。一个问题是,我们这样输出的是1<<x啊,要想输出原来的数x该咋办?是不是还要想办法用常数时间实现log运算呢?哈哈,你又想复杂了!只需要再维护一个数组c,每次读到x时,令c[1<<x]=x即可。到时候呢,直接输出c数组里面的值就可以了。因此,整个算法流程如下:

for (i=0; i<n; i++)
{
    read(x);
    a = a | (1<<x);
    b[1<<x]++;
    c[1<<x] = x;
}
 
while (a > 0)
{
    x = a & (-a);
    for (i=0; i<b[x]; i++) output(c[x]);
    a = a - x;
}

 
    其中,b的“单位宽度”为n的长度,c的“单位宽度”为数据中最大数的长度。这两个数组本身都能用超大整数直接实现。
    另一个问题是,要是输入数据中有负数该咋办?也很简单,只需要在初始时把每个数都加上一个充分大的数,排序完成后再减掉它就行了。

21 条评论

回复给 cgy4ever 取消回复

2  ×    =  2