这是 for 循环 O(1) 还是 O(n)？

Question

给定一个任意大小的数组[] = {0,2,6,...,1000000} 和一段代码：

for i = 0 to size 
    print array[0]

这个 O(1) 是因为它只打印第一项还是 O(n) 因为它打印了 n（大小）次？

Answer 1

这是 O(n)，其中 n 是给定数组的大小。

假设打印一个数组元素需要 1 秒。

如果数组有 1 个元素，程序将打印第一个元素 1 次，所以运行程序需要 1 秒。

如果数组有 10 个元素，程序将打印第一个元素 10 次，因此运行程序需要 10 秒。

如果数组有 100 个元素，程序将打印第一个元素 100 次，因此运行程序需要 100 秒。

运行程序花费的时间随着数组的大小线性增加。因此算法是 O(n).

Answer 2

复杂度为O(n)。

由于这个for循环是从0到size，所以这个for是O(n)。在 for 里面，它 print array[0] 是 O(1).

所以整个段变成 O(n) x O(1) 也就是 O(n)。

它打印第一项 n 次，结果为 O(n)。

例如，想想下面这个简单的赋值代码：

for i = 0 to size
    a = array[0]

同样得到第一项n次，显然是O(n)（忽略任何编译器优化）。

Is this for loop O(1) or O(n)?