打印一个字符串真的需要 O(n) 吗？

Question

我正在做一个来自 Cracking the Coding Interview 的例子，我读到执行 System.out.println(prefix);（其中前缀是一个字符串）需要 "O(n) time since each character needs to be printed"。如果将类似的 print 语句放在 O(1) 算法中（例如散列 table 查找等），它会使整个算法成为 O(n)?

Answer 1

在描述算法的大 O 复杂性时，定义表达式中的变量代表什么是至关重要的。可能经常有好几个！例如，在二叉树中查找一个整数，然后打印与该节点关联的字符串可能被表征为 O(m + log n)，其中 n 是树中对象的数量，m是字符串的长度。

使用单个变量来表示多个不同的因素（例如，散列中元素的数量 table 和它们的大小）总是错误的，这样做会导致明显荒谬的结果（例如，哈希 table 查找是 O(n)）。

Answer 2

我在 Cracking the Coding Interview 中的同一个例子中遇到了这个完全相同的问题。引用的代码行是

void permutation(String str, String prefix) {
  if (str.length() == 0) {
    System.out.println(prefix)
  } else {
    // some for loop recursive code
  }
}

问题后面说 “每个函数调用需要多长时间？执行第 7 行需要 O9n) 时间，因为每个字符都需要打印。” 第 7 行参考打印语句。

知乎上有人给出了很好的解释： https://www.quora.com/What-exactly-is-the-time-complexity-for-System-out-println-in-Java-O-1-or-O-N

To print anything on the screeen one needs to copy it to the "stdout" file. So when we call System.out.println(), it copies the value of its parameter into the stdout file and we know that copying a string will take O(n) where n is the length of the string.
Try this.

for(int i = 0;i < 100000;++i)  
System.out.println("a");

然后试试这个。

for(int i = 0;i < 100000;++i)  
System.out.println("asdhasdyasiluftyiufhiuasydfujshaskljdaklsdhkajsasdjhakjshakjsfgajskgjfgdsajfgasdkjgadviuasgdfmnasdbfjgsdyjakdhggggggggcjhasdfjkgsjkdfgsdfhgdsfdsfgalsdkjfdhkagsdjkasdjd");

If System.out.println()'s time complexity is O(1) both the statements will take nearly same time otherwise you'll see the difference. :)

所以如果 n 是字符串的长度，打印语句是 O(n)。但是如果你有一个散列 table 查找，如果 n 是字符串的长度，那么大 O 将是 n。

打印一个字符串真的需要 O(n) 吗？

Does printing a string really take O(n)?

algorithm

big-o