此题是TAOCP中的5.1.1 Exercise 26
Design an algorithm that computes the inversion table
b_1 b_2 ... b_n corresponding to a given permutation
a_1 a_2 ... a_n of {1,2,3..,n}, where the running time is essentially proportional to
n log (n) on typical computers
书后给出的答案可能需要多读几遍才能理解
基本思路是,按二进制位考察每一个
a_i,从最高位开始,比如计算1到9的排列,则将所有数先分成两组,1,2,……,7为一组,8和9为一组,然后计算不同组数之间的前后关系。同组之间的前后则暂时先不计算。
第二遍,将所有数分成两类,每一类中又分两组,第一类有1,2,3和4,5,6,7两组,第二类有8,9两个数。计算同一类中两组的先后关系,也就是说,4,5,6,7之间的先后暂不计算,但算这4个数和1,2,3之间的先后关系。
第三遍,继续细分成4类 第一类有 两组 1,和2,3, 第二类有4,5,和6,7.第三类有8,9一组
再一遍计算同一类中两组的先后关系。
最后一遍,所有数两两分类:{1},{2,3}{4,5}{6,7}{8,9}每一类中有两个数,计算这两个数的先后关系。
将此4遍的结果加起来,就是最后的结果。
另外其实此题有更直观的解法
先建立空集S, 对排列依次做,取出排列的第i个元素
a_i
求得S中比
a_i大的元素个数
(rank(a_i), 令
{b_a}_i=rank(a_i)
将
a_i放入S中
于是问题就转化为,是否有数据结构可以在
log(n)的时间内做到插入和计算rank的操作,这是可能的,只需要简单修改平衡二叉树,例如AVL树,在每个节点保存左右子树的节点数即可。因为AVL的插入和查找都是
log( n)级别的操作。而加上左右子树节点数后,查找操作可以得出当前树中比目标数大的个数的值。