Space 跳过列表的复杂性是错误的？
Space Complexity of Skip List is Wrong?
维基百科：https://en.wikipedia.org/wiki/Skip_list 说跳表的最差 space 复杂度是 O(n log(n)) 但我完全不同意。
这是我的证明：
每次跳表最多有log(n)层，所以每个新节点最多可以插入log(n)次。如果我们从具有 1 个节点的跳跃列表开始，那么这就是节点总数增长的方式：
也就是说，$n$次插入后的总和为：
比O(n log(n))大很多...（我刚刚证明了S(n)=w(n^2)是矛盾的）
你的困惑是求和两次。
首先，您说总 个节点（而不是新节点）是1->2->3->5->8->... - 然后您将这些数字相加。
但是，n个元素的节点总数是索引为n的系列中的元素，而不是n.[=14之前所有元素的总和=]
维基百科：https://en.wikipedia.org/wiki/Skip_list 说跳表的最差 space 复杂度是 O(n log(n)) 但我完全不同意。
这是我的证明：
每次跳表最多有log(n)层，所以每个新节点最多可以插入log(n)次。如果我们从具有 1 个节点的跳跃列表开始，那么这就是节点总数增长的方式：
也就是说，$n$次插入后的总和为：
比O(n log(n))大很多...（我刚刚证明了S(n)=w(n^2)是矛盾的）
你的困惑是求和两次。
首先，您说总 个节点（而不是新节点）是1->2->3->5->8->... - 然后您将这些数字相加。
但是，n个元素的节点总数是索引为n的系列中的元素，而不是n.[=14之前所有元素的总和=]