使用跳过列表按字母顺序排列的时间复杂度

Question

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

Answer 1

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

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