我可以知道为什么平均情况下插入跳过列表的时间复杂度是 O(log n)，为什么具有 n 个元素的跳过列表的高度很可能是 O(log n)。以及为什么每一层的平均搜索时间是 O(1)。
user1487718
问问题
13577 次
1 回答
2
我可以帮助 O(log n) 部分。
基本上... [跳过列表搜索] 很容易让人联想到数组中的二进制搜索，并且可能是直观理解为什么此列表中访问的最大节点数在 .
于 2012-10-04T18:45:57.903 回答