arrays - 具有递增整数数组的高效算法

Question

我一直在自学 python 中的数据结构，不知道我是否过度思考（或思考不足！）以下问题：

• 我的目标是提出一个有效的算法

• 使用该算法，我的目标是确定整数 i 是否存在，使得 A[i] = i 在递增整数数组中

• 然后我想以大 O 表示法找到运行时间作为 n A 长度的函数？

所以这不只是 O(log n) 的略微修改版本，其函数等效于：f(i) = A[i] - i。我读错了这个问题吗？任何帮助将不胜感激！

Answer 1

注1：因为你说整数在增加，你已经排除了数组中有重复项（否则你会说单调增加）。因此，快速检查是否没有解决方案是第一个元素是否大于 1。换句话说，为了有任何解决方案的机会，第一个元素必须 <= 1。

注2：与注1类似，如果最后一个元素<数组长度，则无解。

一般来说，我认为你能做的最好的就是二进制搜索。您将它困在低和高指数之间，然后检查低和高之间的中间指数。如果 array[middle] 等于 middle，则返回 yes。如果小于middle，则设置left为middle+1。否则，将 right 设置为 middle - 1。如果 left 变为 > right，则返回 no。

运行时间为 O( log n )。

编辑：如果您允许单调增加，算法将不起作用。练习：解释原因。:-)

Answer 2

这是一个有趣的问题:-)

您可以使用二等分来定位a[i] == i：

       0  1  2  3  4  5  6
a = [-10 -5  2  5 12 20 100]

When i = 3,   i < a[i],  so bisect down
When i = 1    i > a[i],  so bisect up
When i = 2    i == a[i], you found the match

运行时间为O(log n)。

Answer 3

• 你是对的。i在您的A大小数组中找到一个元素O(Log A)确实是。

• 但是，您可以做得更好：O(Log A) -> O(1)如果您用内存复杂性换取时间复杂性，这是“优化器”倾向于做的事情。

我的意思是：如果将新的 Array 元素插入“高效”哈希表中，则可以find在恒定时间内实现该功能O(1)

这在很大程度上取决于您要插入的元素：

• 它们是独一无二的吗？想想碰撞
• 你多久一次insert？