data-structures - 使用跳过列表的字母顺序的时间复杂度

Question

使用 skip-list 按字母顺序显示数据的时间复杂度是多少？如果我们使用四节点实现，跳过列表的时间复杂度是多少？

Answer 1

假设您的输入包含N个元素。首先，您必须构建一个跳过列表。单个插入操作的复杂度平均为O(log N)，因此插入 N 个元素的复杂度为O(N * log N)。当构建跳过列表时，此列表中的元素将被排序。因此，为了枚举它们，您只需要访问O(N)中的每个元素。

值得一提的是，skip-list 是基于随机性的。这意味着不能保证单个插入操作的O(log N)复杂度。最坏情况的复杂度是O(N)，这意味着在最坏的情况下，将 N 个元素插入到跳过列表的复杂度是O(N^2)。