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

Question

今天我在复习一些关于算法的旧笔记，这让我开始思考。

Complexity O(1) means execution time for function is independent on data.

所以假设我们有一个函数来添加数组中的所有元素。

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 是数组的最大可能大小。我知道这段代码效率不高我不想讨论这个。但是 operator + 每次被调用的次数相同，并且不受数据大小的影响。

这是否意味着此函数的复杂度为 O(1)？

Answer 1

是的。 O(1)表示常数时间，不是fast/efficient/optimal.

Big-O 复杂度忽略了常量步骤的复杂度。除法（慢）与增量（快）一样 "complex"。

Answer 2

如果您有最大数组大小，那么复杂度将为 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 是数组的最大可能大小（如问题中定义的那样），而不是其他值。

Answer 3

实际答案是"it depends"。

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

ARRAY_MAX_SIZE 次，你：
- 递增并测试一个 for 循环
- 加入总数
array.length次，你：；
- 访问array[i]
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]是访问内存，而memory is comparatively very slow:

Answer 4

唯一有趣的部分是 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;
}

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

Is time complexity for this function is O(1)?

algorithm

big-o

time-complexity