5

所以我读了一些关于跳过列表的内容,目前正在实施一个。但是到目前为止,我还没有真正做到一件事。为什么跳过列表是随机的?在所有来源中,我发现跳过列表使用随机数来决定将插入项目的级别。不能计算出最优值吗?或者你不能只说“每四个项目”应该插入到上面的级别吗?

4

1 回答 1

4

跳过列表可以确定性地构建,例如以最小化摊销访问成本。但是,对于任何确定性构造方法,高级列表条目的集合始终是已知的,因此很容易构造一个“敌对”的删除操作集,这会将性能退化回 O(n)。通过随机构造,仍然存在一组最坏情况删除,但对于任何相当大的列表,完全偶然发现最坏情况删除序列的可能性微乎其微。

于 2013-07-15T14:10:48.960 回答