这个函数的时间复杂度是O(1)吗？

Question

今天我在复习一些有关算法的旧笔记，这引起了我的思考。

复杂度O(1)意味着函数的执行时间与数据无关。

现在我们假设有一个函数用于将数组中的所有元素相加。

int add(int[] array){
    int sum =0;
    for (int i=0;i<ARRAY_MAX_SIZE;i++){
      sum= sum + (i<array.length?array[i]:0);
    }
    return sum;
}

其中ARRAY_MAX_SIZE是数组的最大可能大小。我知道这段代码不够高效，但我不想讨论这个问题。但是操作符+每次被调用的次数相同，并且不受数据大小的影响。

这是否意味着该函数的复杂度为O（1）？

- user902383

---

复杂度为 O(ARRAY_MAX_SIZE)。如果 ARRAY_MAX_SIZE 是一个常数，那么 O(ARRAY_MAX_SIZE) == O(1)。 - Eric

@Eric，这正是我所想的，但我的某个部分无法接受这一点。 - user902383

实际上，这并不总是正确的。请看我的答案。 - Eric

这就是为什么你不应该将大O应用到代码上（算法可以，但实现不可以），你总是可以争辩说要么事情不会终止，要么它在最多一些“常数但也许荒谬”的步骤内终止。一旦你决定了指针的大小，你就进入了一个有限状态机，而不是图灵机。 - harold

Answer 1

是的，O(1)表示常数时间，而不是快速/高效/最优。

大O复杂度忽略了常数步骤的复杂性。除法（慢）和递增（快）一样“复杂”。

- Amit

---

你说得对，我不知道为什么，但我认为O(1)比O(N)更有效率，这显然是错误的假设，导致我提出了这个愚蠢的问题。感谢您的快速回答。 - user902383

我认为*O(0.001)*已经被视为不仅是常数，而且也很快了 :-) - Ami Tavory

Answer 2

实际答案是“取决于情况”。

这里有两组不同的事情发生：

1. 对于`ARRAY_MAX_SIZE`次，您：

- 增加并测试一个for循环 - 添加到总数中

2. 对于`array.length`次，您：

- 访问`array[i]`

3. 对于`ARRAY_MAX_SIZE - array.length`次，您：

- 加载常量零

因此，总运行时间为：

t = k_1 * ARRAY_MAX_SIZE +
    k_2 * n +
    k_3 * (ARRAY_MAX_SIZE - n)

所以你要比较k_2和k_3。它们基本相等吗？那么就是O(1)。是k_2 >> k_3吗？那么就是O(n)。

为什么可能会出现k_2 >> k_3？因为array[i]正在访问内存，而内存相对来说非常慢：

- Eric

Answer 3

唯一有趣的部分是array[i]只使用了n次。这意味着您添加一个操作来推迟引用数组以仅获取第i个元素n次。我通常不会计算这个，但这可能会使它成为O(n)吗？只是抛出反面观点。

我想这应该是真正的O(1)等效。

int add(int[] array){
    int sum =0;
    int len = array.length;
    for (int i=0;i<ARRAY_MAX_SIZE;i++){
        sum= sum + array[i%len] & (i < len ? 0xFFFFFFFF : 0);
    }
    return sum;
}

- SGM1

---

我在:的一侧看到了一次array[，而在另一侧看到了两次。哪一侧被执行取决于数组的长度。 - Eric

@Eric 是的，所以每次使用代码时，恰好有 (1 + 2) * SOME_CONSTANT * ARRAY_MAX_SIZE = O(1) 次计算/迭代。 - SGM1

没有，因为 ? : 运算符是短路运算符，只有其中一个结果会被计算。因此，一侧的计算比另一侧多，而这个差异由 n 决定。 - Eric

@Eric 你说得对，已经修复了，希望可以正常工作。感谢提醒。 - SGM1

通过执行 array[i%len] & (i < len ? 0xFFFFFFFF : 0) 来使它更加明显。 - Eric

Answer 4

如果您有一个最大数组大小，则复杂度将为O(1)。但这会带来其他后果。array.length需要小于ARRAY_MAX_SIZE，因此array.length受到常数的限制，使得以下内容也是O(1)：

for(int i=0; i<array.length; i++) {
    sum = sum + array[i];
}

因此，我们通常会忽略数组大小的限制，以获得算法复杂度的有用结果。

显然，这是假设ARRAY_MAX_SIZE是数组的最大可能大小（正如在问题中定义的那样），而不是其他值。

- fgb

---

这里不需要 array.length 小于 ARRAY_MAX_SIZE 才能“工作”。 - Amit

@Amit 怎么不行呢？长度必须小于最大长度，否则就不是最大长度了。 - fgb

你把值和标题搞混了。有什么阻止 array.length > ARRAY_MAX_SIZE 的吗？ - Amit

我猜如果你想的话，可以随意给变量赋错误的值，但基于那样的分析是毫无意义的。 - fgb