-1
두 레벨 만있는 일정한 간격 크기를 가진 "완벽한"skiplist를 만들기 위해 노력하고 있습니다. 서로 다른 크기의 skiplists에 대한 방문한 노드를 계산할 때 크기에 따라 결정된다는 것을 알 수 있지만이를 계산하기 위해 n과 관련된 수식을 사용할 수 없습니다.두 레벨 만있는 결정 론적 skiplist의 최적 갭 크기 찾기
A
답변
1
실제로 일정 간격 크기를 원할 경우 최적 간격 크기는 목록 길이의 제곱근입니다. 예를 들어, 건너 뛰기 목록이 16 개 항목 인 경우 최적 간격 크기는 4입니다. 15 번째 항목을 얻으려면 3 번의 점프와 3 번의 점프를 수행하십시오. 그것은 최악의 경우입니다.
k 번째 항목으로 이동하려면 k/sqrt(n) + k%sqrt(n) 링크를 따르십시오.
더 큰 간격 크기는 더 빨리 끝낼 수 있지만 목록 내의 어느 곳으로 가려면 더 많은 단일 링크를 따라야 할 수 있습니다. 평균적으로 더 많은 링크를 따라갈 것입니다. 틈새 크기가 작을수록 단일 링크는 더 적지 만 더 긴 링크는 따릅니다.
귀하의 목록이 1,000,000 개 항목이면 간격 크기는 1,000이어야합니다.
귀하의 점근 적 복잡성은 고정 된 두 번째 레벨로 단일 링크 된 목록의 O (n)에서 O (sqrt (n))로 이동합니다. 그것은 두 단계로 할 수있는 최선의 방법입니다.
+0
)의 가능한 복제 그게 완벽한 설명입니다. 감사! – moo
[Two Egg Problem Confusion] ([https://stackoverflow.com/questions/4171966/two-egg-problem-confusion] – Paul