java - System.out.println 的时间复杂度是多少？

Question

假设代码如下:

String[] arr = {"Cat", "Dog", "Maple", "Blue"};

for (String str : arr) {
    System.out.println(str);
}

在这种情况下时间复杂度是 O(N) 还是 O(N^2)？

乍一看，似乎是 O(N)，但我想了想，由于 str 不是常数，所以在这种情况下是 O(N^2) 吗？

Answer 1

for 循环的时间复杂度为 O(n)，其中 n 是数组的大小。

System.out.println() 需要 O(k) 时间打印 k 个字符，即上述部分的平均时间复杂度代码应该是O(nk);

System.out.println内部使用以下代码:

public void write(String str, int off, int len) throws IOException {
    synchronized (lock) {
        char cbuf[];
        if (len <= WRITE_BUFFER_SIZE) {
            if (writeBuffer == null) {
                writeBuffer = new char[WRITE_BUFFER_SIZE];
            }
            cbuf = writeBuffer;
        } else {    // Don't permanently allocate very large buffers.
            cbuf = new char[len];
        }
        str.getChars(off, (off + len), cbuf, 0);
        write(cbuf, 0, len);
    }
}