下面的方法的运行时如何是O(N)而空间复杂度是O(1)？

Question

任何人都可以解释下面描述的给定问题的方法如何在O(N)时间和O(1)空间中运行？

问题:给定2个排序数组,找到共同的元素数.数组长度相同,每个都有不同的元素.

以下面的2个数组为例:

A: 13, 27, 35, 40, 49, 55, 59
B: 17, 35, 39, 40, 55, 58, 60

1. 在B中对A [0] = 13进行线性搜索.从B [0] = 17开始.停止在B [0] = 17.未找到
2. 在B中对A [1] = 27进行线性搜索.从B [0] = 17开始.在B [1] = 35处停止未找到
3. 在B中对A [2] = 35进行线性搜索.从B [1] = 35开始.在B [1] = 35处停止
4. 在B中对A [3] = 40进行线性搜索.从B [2] = 39开始.在B [3] = 40处停止
5. 在B中对A [4] = 49进行线性搜索.从B [3] = 40开始.在B [4] = 55处停止.

我很困惑我们正在进行线性循环的部分,以获得A的所有元素已经制作O(N)时间,然后再次在B中进行线性搜索以找到元素.B中的班轮搜索正在最后一个停止的地方.这不会使给定方法的时间复杂度为O(N ^ 2)吗？如果没有,为什么？

Answer 1

这是合并算法的变体,除了没有构造输出序列,并且使用线性搜索将列表前进到下一个位置,而不是一次一个元素.

如果N是两个列表中元素的总数,则合并在时间上是O(N),在空间中是O(N).空间要求来自存储输出序列的需要,而算法不会这样做.因此,您的算法在时间上保持为O(N),并在空间要求中变为O(1).