Geek asks and answers

Expected Space Consumption by Skip Lists

What is the expected space used by the skip list after inserting n elements?

I expect that in the worst case, space consumption can grow unlimitedly.

Wikipedia says "Space O (n)".

How can this be proved anyway?

+3
source share
2 answers

In accordance with this thesis , which I find more reliable than wikipedia, Wikipedia is erroneous . A probabilistic skip list is the Theta(nlogn)worst complexity of the space.

, PSL , Theta (n lg n) Theta (n)

, f(n) , f(n) = O(logn), , . , f(n) , O(nlogn) , O(nlogn), O(n).

:
, , , :
"" node "" .

E(#nodes) = Sigma(E(#nodes_for_column_i)) (i in [1,n])

, .

E(#nodes_for_column_i) = 1 + 1/2 + ... + 1/n < 2 ( i). , 1 1 node, p = 1/2, node. p '= 1/2, node (total p * p' = 1/4),.... , :

E(#nodes) = n*E(#nodes_for_each_column) = n*(1+1/2+...+1/n) < 2n = O(n)
+3

N . :

N 1, N/2 2, N/4 3 ..

N + N/2 + N/4 + N/8 +.. N/2 ^ k , 2N, N * SizeOf (Data) + 2 * N * SizeOf (Pointer) = O (N).

, .

0

More articles:


All Articles