这个算法没有二次运行时间吗？

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