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

Question

我一直在自学Python中的数据结构，不确定我是否过度思考（或者欠缺思考！）以下问题：

• 我的目标是设计一个高效的算法

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

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

所以，这难道不只是稍微修改了O（log n）的版本，并且具有等于：f(i) = A [i] - i的函数吗？我是否错误地阅读了这个问题？任何帮助都将不胜感激！

- WycG

---

写一些代码作为开始 :) 你对复杂性的推理似乎是正确的。 - Ashalynd

属于程序员SE，不属于这里。 - user93353

这归结为在函数中寻找零点，其中f(x) = A[x] - x。使用二分法只是一种可能的方法，另一种方法是在两个边缘之间使用线性逼近来找到零点的可能位置。 - Ulrich Eckhardt

Answer 1

注意1：因为你说整数是递增的，所以你排除了数组中有重复项的可能性（否则你会说单调递增）。因此，一个快速检查是否没有解决方案的方法是如果第一个元素大于1，则不可能有解决方案。换句话说，要有任何解决方案的机会，第一个元素必须小于等于1。

注意2：与注意1类似，如果最后一个元素小于数组长度，则没有解决方案。

总的来说，我认为最好的方法是二分查找。将其限制在低和高索引之间，然后检查低和高之间的中间索引。如果array[middle]等于middle，则返回yes。如果它小于middle，则将左指针设置为middle+1。否则，将右指针设置为middle-1。如果left>right，则返回no。

运行时间为O(log n)。

编辑：如果允许单调递增，该算法将无法工作。练习：解释原因。 :-)

- TheGreatContini

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)。

- Raymond Hettinger

Answer 3

• 你说得对。在大小为A的数组中查找元素i确实是O(Log A)。

• 然而，你可以做得更好：如果你愿意用时间复杂度换取空间复杂度，也就是“优化器”通常所做的事情，那么O(Log A) -> O(1)是可以实现的。

我的意思是：如果你将新的数组元素插入到一个“高效”的哈希表中，你可以在常数时间O(1)内完成查找操作。

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

• 它们是唯一的吗？考虑到碰撞
• 你有多频繁地进行insert操作？

- AK_