跳表最坏空间复杂度nlog(n)正确性论证及非O(n)证明问询

在跳表（Skip List）中：

• 最大高度为log(n)，其中n为跳表中叶子节点的数量。
• 因此最坏情况下，每个节点会被添加*log(n)*次。

有观点认为「跳表最坏空间复杂度为nlog(n)」的表述不准确，理由是不同运行场景下n的值会发生变化。以下将证明跳表的最坏空间复杂度确实为nlog(n)，且进一步明确其最坏空间复杂度不属于O(n)。

参考推导示例 #

初始仅1个节点时，最多可新增*log(1)层，总节点数为2；新增1个节点时最多可新增log(2)层，总节点数为3；再新增1个节点时最多可新增向上取整的log(3)*层，总节点数为5。

前几项元素序列（对应每个新增节点的新增层数）如下：
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5...

通用推导公式 #

总节点数计算公式为：
S(n) = Σ（i从1到n）⌈log₂i⌉
对该式做上下界分析可得：

• 上界：S(n) ≤ n * ⌈log₂n⌉ = O(nlogn)
• 下界：至少有一半的节点高度≥2，四分之一的节点高度≥3，以此类推累加可得S(n) ≥ nlogn / 2 = Ω(nlogn)

由此可证跳表最坏空间复杂度为Θ(nlogn)，不存在常数k使得总节点数≤kn，因此不属于O(n)。

内容的提问来源于stack exchange，提问作者Dan