1

私はのための最良のアルゴリズムを見つけようとしています

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

。

の定義がideal skip list、最初のレベルにすべての要素がある場合、上のレベルにはそれらの半分、次のレベルにはそれらの4分の1などがあります。

O(n)特定のノードであるかどうかに関係なく、元のリンクリストの各ノードにコインを投げて、上に行くかどうかに関係なく、現在のノードの2階に別の複製ノードを作成するランタイムについて考えています。 。最終的に、このアルゴリズムはO（n）を生成しますが、より良いアルゴリズムはありますか？

よろしく

4

1 に答える 1

1

リンクされたリストはソートされていると想定しています-そうでない場合は、ソートする必要があるため、比較ベースのアルゴリズムでは実行できませんOmega(nlogn)

  • リストの「最上位」で繰り返し、2 つおきのノードに「リンク アップ ノード」を追加します。
  • 最高レベルにノードが 1 つだけになるまで繰り返します。

アイデアは、元のサイズの半分の新しいリストを生成し、2 つおきのリンクで元のリストにリンクし、サイズ 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)少なくとも、元のリストの後半に少なくとも 1 つのノードを追加する必要があり、そこにたどり着くのはそれ自体であるため、それよりもうまく実行できないことは簡単にわかります。O(n)

于 2012-04-28T20:33:31.527 に答える