首页 > 试题广场 >

一个长度为 n 的正整数数列,先递减再递增,如果要找到数列中

[单选题]

一个长度为 n 的正整数数列,先递减再递增,如果要找到数列中最小的正整数,最优算法的平均时间复杂度是?

  • O(n)
  • O(nlog(n))
  • O(n^2)
  • O(log(n))
二分法找中点,中点左右两边数都比中点大就结束,否则就向较低的一边搜索
发表于 2019-04-15 20:15:44 回复(3)
二分法
发表于 2019-04-03 23:17:07 回复(0)
根据big-O notation 的定义,C和D两个选项不是等价的吗?
发表于 2019-06-01 13:56:25 回复(1)
折半查找法,平均时间复杂度O(logn)
发表于 2021-05-29 10:08:45 回复(0)
二分法要求数组有序,这种情况怎么二分?
发表于 2023-05-11 23:22:06 回复(0)
不考虑线段树的建树复杂度,查询复杂度是O(logn)
发表于 2021-03-29 00:20:30 回复(0)
二分法,左右两边比较,如果小于就左区间找,大于就右区间找,等于就左或者又循环找直到小于或大于,如果找到边界要注意判断数组越界
发表于 2021-02-06 09:43:33 回复(0)
d
发表于 2019-11-23 21:03:50 回复(0)
先减后增找最小,说二分法的可以分给我看看嘛
发表于 2019-05-29 21:27:11 回复(0)
感觉有点问题,因为每次要跟左右两边都比较一次。每次比两次,然后二分法下来大概要log n 次,所以是 2*log(n) = log(n^2)。实际上,用大O语言,log(n^2) 和 log(n) 是一个意思呀。。
发表于 2019-04-24 20:56:56 回复(1)
这个题,我在想,用堆行不行呢,我们知道,将新来的元素插入堆中的时间复杂度是log(i-1),其中i-1是当前元素的之前的(i-1)个元素;所以建堆的时间复杂度是,log1+log2+log3+.....log(n-1)=-------O(n)----------!!!!!即建堆的时间复杂度是线性的。但是我们的答案里有更小的log(n),于是我在想,有没有更快的方法呢?答案是有:即二分法,二分法的时间复杂度就认为是logn即可,虽然在这里使用二分法,我没搞明白不是完全有序,我该怎么用。

发表于 2019-04-13 16:10:07 回复(2)