건너 뛰기 목록의 예상 공간 사용량

Question

n 요소를 삽입 한 후 건너 뛰기 목록에서 사용 된 예상 범위는입니까?

최악의 경우 공간 소비가 무한히 증가 할 것으로 예상됩니다.

위키 피 디아는 "우주 O (n)"라고 말합니다.

어떻게 이것이 다른 방법으로 입증 될 수 있습니까?

Answer 1

this thesis에 따르면, 나는 위키 백과, 위키 피 디아가 더 정확하다는 것을 발견했다.. 확률 스킵 목록은 Theta(nlogn) 최악의 경우의 공간 복잡성입니다. 평균의 PSL은 또한 합리적으로 수행 최악의 경우 있음에도 불구

의 세타 (N 엑스 N) 공간 및 세타 (n)은 시간 복잡도가 높아지는 것을

있다 최악의 경우는 f(n) 수의 숫자로 제한 할 수 있기 때문에 무한하지 않습니다. f(n) = O(logn)이며,이 높이에 도달하면 동전을 뒤집기를 중지하십시오. 따라서 f(n) 개의 행이있는 경우 전체 노드 수는 O(nlogn)이므로이 경우 공간 복잡도는 O(nlogn)이며 O(n)이 아닙니다.

---

편집 :
당신이 예상 공간 소비를 찾고, 그리고 경우하지 최악의로 처음 그 질문에 언급했다 :
은 이제 바닥 노드로 "열"을 나타 내기하자 모든 노드가 "위로"있습니다.

상기 식은 기대 값의 선형성 때문에 참이다.

E(#nodes_for_column_i) = 1 + 1/2 + ... + 1/n < 2 (각 i에 대해). 확률 1의 경우 p = 1/2 인 노드가 1 개 있기 때문에 각각에 추가 노드가 있기 때문입니다. P와 '(= 4분의 1 = 1/2이 각각 총 P는 * P는) 추가 노드를 갖는'.... 따라서 우리는 유도 할 수있다 :

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

Answer 2

하자 우리는 N으로 결정 skiplist을 노드. 데이터 값에 추가하여,리스트가 포함 등급 1

N 포인터 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 (엔).

레벨 간 링크는 고려하지 않았지만 포인터 수와 관련이 있습니다.