Идеал Пропустить лист? O (n) время выполнения?

Question

Я пытаюсь найти лучший алгоритм для

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

.

В тех случаях, когда определение ideal skip list состоит в том, что на первом уровне у нас будут все элементы на уровне выше - половина из них, одна за четвертью их ... и так далее.

Я думаю о O(n) время выполнения, где с участием бросал монетку для каждого узла в оригинального связанный список, или нет для конкретного узла, я должен идти или нет, и создать еще один дубликат узла текущий узел наверху ... В конечном итоге этот алгоритм произведет 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 (п), так как сложность алгоритма может быть описана как T(n) = n + T(n/2), таким образом, вы получите T(n) = n + n/2 + n/4 + ... -> 2n

Легко видеть, что это не может быть сделано лучше затем O(n), так как по крайней мере вам нужно будет добавить хотя бы один узел во второй половине исходного списка, а сам получить его O(n)