algorithm - 理想的跳过列表？ O(n) 运行时间？

Question

我正在尝试为

找到最佳算法

converting an "ordinary" linked list 
into an `ideal skip list`

.

ideal skip list 的定义是，在第一层我们将拥有所有元素，在一半以上的水平，四分之一之后的水平......等等。

我正在考虑 O(n) 运行时，其中涉及为每个节点 throw 硬币原来的链表，不管是不是针对某个特定的节点，是不是要上去，为楼上的当前节点再创建一个重复的节点...最终这个算法会产生 O(n) ，有没有更好的算法？

问候

Answer 1

我假设链表已排序 - 否则无法在基于比较的算法中完成，因为您需要在 Omega(nlogn)

中对其进行排序

• 迭代列表的“最高级别”，每隔一个节点添加一个“链接节点”。
• 重复直到最高层只有一个节点。

想法是生成一个新列表，其大小是原始列表的一半，在每个第二个链接中都链接到原始列表，然后在较小的列表上递归调用，直到达到大小为 1 的列表。
你最终会得到大小为 1,2,4,...,n/2 的列表，这些列表相互链接。

伪代码:

makeSkipList(list):
  if (list == null || list.next == null): //stop clause - a list of size 1
      return
//root is the next level list, which will have n/2 elements.
  root <- new link node
  root.linkedNode <- list //linked node is linking "down" in the skip list.
  root.next <- null //next is linking "right" in the skip list.
  lastLinkNode <- root
  i <- 1
//we create a link every second element
  for each node in list, exlude the first element:
     if (i++ %2 == 0): //for every 2nd element, create a link node.
         lastLinkNode.next <- new link node 
         lastLinkNode <- lastLinkNode.next //setting the "down" field to the element in the list
         lastLinkNode.linkedNode <- node 
         lastLinkNode.next <- null
   makeSkipList(root) //recursively invoke on the new list, which is of size n/2.

复杂度为 O(n)，因为算法复杂度可以描述为 T(n) = n + T(n/2)，因此您得到 T(n) = n + n/2 + n/4 + ... -> 2n

很容易看出它不能比 O(n) 做得更好，因为至少你必须在原始列表的后半部分添加至少一个节点，并且到达那里本身就是 O(n)