为什么这段代码给出 big-O = O(1)

Question

public static LinkedList third(int[] array){
    LinkedList retval = null;
    for (int i = 0; i < 999 && i < array.length; i = i + 1) {
        retval = new LinkedList(array[i], retval);
    }
    return retval;
}

为什么这段代码给出 big-O = O(1)？

Answer 1

因为循环将最多执行 999 次，这是一个常数值，因此您可以认为它是 O(999) = O(1) = O(c)，其中 c 是一个常数值。

如果i的值不受999的限制，循环将执行array.length次，复杂度为O(n)，其中n是输入的大小大批。

为什么这段代码给出 big-O = O(1)

Why this code gives big-O = O(1)

big-o