5

给定一个数组，使其元素的值从第 0 个索引增加到某个 ( k -1) 索引。在k处，该值最小，然后通过第n个元素再次开始增加。找到最小元素。

本质上，它的一个排序列表附加到另一个列表；示例：（1、2、3、4、0、1、2、3 ）。

我尝试了各种算法，例如构建最小堆、快速选择或只是简单的遍历。但不能低于 O(n)。但是这个数组中有一个模式，表明二进制搜索类型的东西应该是可能的，复杂性应该是 O(log n) 之类的东西，但找不到任何东西。想法？？

谢谢

4

4 回答 4

4

否 下降可以在任何地方，这没有结构。

考虑极端情况

1234567890
9012345678
1234056789
1357024689

它简化为找到最小元素。

于 2011-09-28T18:57:14.257 回答
1

对递减范围进行广度二进制搜索，在二进制拆分处有一个元素重叠。换句话说，如果你有 17 个元素，比较元素

0,8
8,16
0,4
4,8
8,12
12,16
0,2
2,4

等等，寻找左元素大于右元素的情况。

一旦找到这样的范围，递归，在该范围内执行相同的二进制搜索。重复直到找到递减的相邻对。

平均复杂度不小于 O(log n)，最坏情况为 O(n)。谁能得到更严格的平均复杂度估计？它似乎大致介于 O(log n) 和 O(n) 之间，但我不知道如何评估它。它还取决于对值范围和从一个成员到下一个成员的增量大小的任何附加约束。

如果元素之间的增量始终为 1，则存在 O(log n) 解。

于 2011-09-28T20:25:40.453 回答
1

它不能在少于 O(n) 的时间内完成。

这种最坏的情况会一直困扰着我们——

递增列表 a1,a2,a3....ak,ak+1... an

只有一个偏差 ak < ak-1 例如 1,2,3,4,5,6,4,7,8,9,10

所有其他数字都包含关于“k”或“ak”值的绝对零信息

于 2011-09-29T03:22:58.430 回答
0

最简单的解决方案是向前查找列表直到下一个值小于当前值，或者向后查找大于当前值的值。即 O(n)。

同时执行两者仍然是 O(n) 但运行时间可能会更快（取决于复杂的处理器/缓存因素）。

我不认为你可以在算法上比 O(n) 更快地得到它，因为许多分而治之的搜索算法依赖于有一个排序的数据集。

于 2011-09-29T04:13:20.237 回答