Ideal跳过列表？ O（n）运行时间？

我试图找到Ideal跳过列表？ O（n）运行时间？

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

最好的算法。

其中ideal skip list的定义是在第一个层次中，我们将在所有级别中包含所有元素 - 其中一半为其中的一个，后一个为四分之一......等等。

我在想O(n)运行时间，其中包括投掷每个节点的硬币原始链接列表，无论是否为特定的节点，我应该去涨不跌，并创建另一个重复的节点楼上的当前节点... 最终这个算法会产生O（n），有没有更好的算法？

问候

来源

2012-04-28 ron

请参阅[wiki页面]（http://en.wikipedia.org/wiki/Skip_list），了解您提到的随机算法 – HelloWorld 2012-04-28 19:29:35

我假设链接列表进行排序 - 否则它不能在基于比较算法来完成，因为你需要它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.

复杂性是因为算法复杂度可以描述为T(n) = n + T(n/2)为O（n），这样你可以获得T(n) = n + n/2 + n/4 + ... -> 2n

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

来源

2012-04-28 20:33:31 amit

“最高级别”是什么意思？我从第0级开始（完整的原始链表），然后在第一个节点之后采用这个节点，即我在“头”之后取和节点，然后我上去为它放置一个新节点，在楼上？你的算法对我来说不是很清楚....你能解释一下吗？ – ron 2012-04-28 22:26:55

@ron：我editted答案，并添加描述递归函数注释伪码，这个想法是 - 创建大小为n/2的跳跃列表一个链接，然后递归调用你的小名单上，直到你得到一个列表大小为1，您将以大小列表结束：1，2，4，...，n/2，n – amit 2012-04-28 22:49:00

Ideal跳过列表？ O（n）运行时间？

回答

相关问题