n次登录n次混洗链表的算法

接下来呢？执行与合并排序相同的过程。合并时，不要从两个列表中按排序顺序选择一个元素（而是一个一个），而是掷硬币。根据掷硬币的结果，选择从第一个列表中选择元素还是从第二个列表中选择元素。

算法。

shuffle(list):    if list contains a single element        return list    list1,list2 = [],[]    while list not empty:        move front element from list to list1        if list not empty: move front element from list to list2    shuffle(list1)    shuffle(list2)    if length(list2) < length(list1):        i = pick a number uniformly at random in [0..length(list2)]          insert a dummy node into list2 at location i    # merge    while list1 and list2 are not empty:        if coin flip is Heads: move front element from list1 to list        else: move front element from list2 to list    if list1 not empty: append list1 to list    if list2 not empty: append list2 to list    remove the dummy node from list

空间的关键点是将列表分为两部分不需要任何额外的空间。我们唯一需要的额外空间是在递归过程中在堆栈上维护log n个元素。

虚拟节点的意义在于要认识到，插入和删除虚拟元素可以使元素的分布保持均匀。

分析。 为什么分布均匀？在最终合并之后，

P_i(n)

i

• i

  排在自己列表的第4位，并且该列表首次赢得了抛硬币

  i

  ，这种可能性为

  1/2^i

  ;

• i-1

  排在自己列表的第一个位置，该列表赢得了 包括最后一次 掷硬币的

  i-1

  次数 ， 并且输掉了一次，这的概率是

  (i-1) choose 1

  次

  1/2^i

  ；
• 在

  i-2

  它自己的列表中排在第二位，该列表赢得了 包括最后一次 掷硬币的

  i-2

  次数并输了两次，这的概率是次； __

  (i-1) choose 2``1/2^i

• 等等。

所以概率

P_i(n) = sum_{j=0}^{i-1} (i-1 choose j) * 1/2^i * P_j(n/2).

归纳地，您可以证明

P_i(n) = 1/n

P_j(n/2) = 2/n

sum_{j=0}^{i-1} (i-1choose j)

i-1

2^{i-1}

P_i(n) = sum_{j=0}^{i-1} (i-1 choose j) * 1/2^i * 2/n       = 2/n * 1/2^i * sum_{j=0}^{i-1} (i-1 choose j)       = 1/n * 1/2^{i-1} * 2^{i-1}       = 1/n

我希望这是有道理的。我们唯一需要的假设

n

PS我的直觉远未达到严格要求，但为防万一。想象一下，我们将1到n之间的数字随机分配给列表的元素。现在，我们针对这些数字进行合并排序。在合并的任何给定步骤中，都需要确定两个列表中哪个头较小。但是一个大于另一个的概率应该恰好是1/2，因此我们可以通过掷硬币来模拟。

PPS是否可以在此处嵌入LaTeX？