2
그래서 나는 확률 스킵리스트 공간 사용에 대한이 질문 보았다 : (answer)확률 스킵 목록 공간의 복잡성
을하지만 나는 그가 예상 접근 또는 최악의 경우 접근 방식을 원한다면 아스 커는 분명하지 않다 생각합니다.
저는이 질문을 다시 토론에 올리고 싶습니다. 왜 내가 혼란스러워하는지 설명 할 것입니다.
명확하게 - 나는 의 최악의 사례에있는 확률 적 건너 뛰기 목록의 공간 복잡성을 찾고 있습니다.
한편, 최대 레벨 수는 log (n)이라고 가정합니다. 최악의 경우에 우리는 각 레벨에 n 개의 노드가있을 수 있다고 추측하기 쉽습니다. O (n logn). 한편 log (n) 수준 (예 : 목록) 이상일 수 있다고 가정하고 그 경계를 n으로 설정 한 다음 n을 얻습니다. n => O (n^2)
그러나! 나는 레벨을 제한 할 권리가 왜 있는지 이해하지 못한다. 새로운 레벨이 동전 던지기에 달려있다면, 최악의 경우에 우리는 새로운 레벨 (즉, 새로운 레벨)을 얻게 될 것이다. 심지어 묶여 있지 않아?! 혼란 스럽습니다.
감사합니다. –