algorithm - 该算法没有二次运行时间，对吗？

Question

我最近接受了一次面试，遇到了一个小问题，我要编写代码。

问题基本上是在长度为 n 的数组中找到重复项，使用 O(n) 中的常量空间。每个元素都在 1-(n-1) 范围内并且保证是重复的。这是我想出的:

public int findDuplicate(int[] vals) {
    int indexSum=0;
    int valSum=0;   
    for (int i=0; i< vals.length; i++) {
         indexSum += i;
         valSum += vals[i];
    }
    return valSum - indexSum;
}

然后我们讨论了这个算法的运行时间。从 0 -> n = (n^2 + n)/2 的系列之和是二次的。但是，算法不是O(n) 时间吗？操作的数量受数组长度的限制，对吧？

我错过了什么？这个算法是O(n^2)吗？

Answer 1

从 0 到 n 的整数之和为 O(n^2) 的事实在这里无关紧要。

是的，您在循环中运行了 O(n) 次。

最大的问题是，您假设加法的复杂度顺序是什么？

如果 O(1) 那么是的，这是线性的。大多数人会假设加法是 O(1)。

但是如果加法实际上是 O(b)(b 是位，在我们的例子中是 b = log n)怎么办？如果你要假设这个，那么这个算法实际上是 O(n * log n)(添加 n 个数，每个需要 log n位来表示)。

同样，大多数人假设加法是 O(1)。