问跳表的时间复杂度
EN

Stack Overflow用户

提问于 2012-10-05 02:36:58

回答 1查看 13.1K关注 0票数 3

我想知道为什么在平均情况下跳表插入的时间复杂度是O(log )，为什么n个元素的跳表的高度大概率是O(log )。以及为什么每层的平均搜索时间是O(1)。

algorithm

data-structures

skip-lists

回答 1

Stack Overflow用户

回答已采纳

发布于 2012-10-05 02:45:58

我可以帮助处理O(log )部分。

基本上..。[Skip list searching] is quite reminiscent of binary search in an array and is perhaps the best way to intuitively understand why the maximum number of nodes visited in this list is in .

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/12733622

复制

相似问题

问跳表的时间复杂度
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问跳表的时间复杂度EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问跳表的时间复杂度
EN