首页 > 试题广场 >

类似跳表的数据结构查找元素的时间复杂度是？

[单选题]
有如下一个类似跳表的数据结构：每层都是已经排好序的链表，level1层的链表有所有元素，levelN层的链表只有levelN-1的1半的元素，levelN层的结点指向levelN-1层中相同的结点。请问查找一个元素的时间复杂度是： 
  • O(logn)
  • O(n)
  • O(nlogn)
  • O(n^2)
查看正确选项
添加回答
可笑痴狂头像 可笑痴狂
二分查找时间复杂度计算：

总共有n个元素，

渐渐跟下去就是n,n/2,n/4,....n/2^k，其中k就是循环的次数

由于你n/2^k取整后>=1

即令n/2^k=1

可得k=log2n,（是以2为底，n的对数）

所以时间复杂度可以表示O()=O(logn)

发表于 2015-12-30 15:00:10 回复(1)
小乌头像 小乌
链表也可以二分查找吗
发表于 2016-09-17 19:08:20 回复(0)
陋室头像 陋室
基本的二分查找时间复杂度O(logn)
发表于 2015-09-08 15:51:54 回复(1)
牛客303136号头像 牛客303136号
这样查找肯定不会比顺序查找慢，顺序查找的时间复杂度为O(n)，这个肯定小于O(n)
发表于 2016-09-01 20:30:03 回复(0)
Ｍe怤畢炜eＭ头像 Ｍe怤畢炜eＭ
看着好像二分查找
发表于 2016-08-19 08:14:22 回复(0)
牛客560221号头像 牛客560221号
所以查找入口应该是level4的那个1结点是嘛？
发表于 2018-03-24 09:47:15 回复(0)
幸福长大了头像 幸福长大了
二分查找时间复杂度计算：

总共有n个元素，

渐渐跟下去就是n,n/2,n/4,....n/2^k，其中k就是循环的次数

由于你n/2^k取整后>=1

即令n/2^k=1

可得k=log2n,（是以2为底，n的对数）

所以时间复杂度可以表示O()=O(logn)

发表于 2017-05-31 20:06:15 回复(0)
提交观点

问题信息

高级结构
来自：腾讯2016研发工程师...
难度：
7条回答 16738浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号