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）運行時間？

回答

相關問題