system.out.println的时间复杂度

Question

在我的算法课程中,我被告知不同的事情,并且想知道我是否可以得到关于Java的System.out.println()命令的时间复杂性的明确答案.

例如,对于N,下面的时间复杂度是多少？

String stringy = "";
while(stringy.length() < N) {
    System.out.println(stringy);
    stringy += "X";
}

谢谢你帮助新人!

Answer 1

我运行了一个基本的 python 程序来检查Python中打印语句的时间复杂度，以打印可变数量的字符。代码如下 -

import time

def current_milli_time():
    return round(time.time() * 1000)

=====================================

startTime1 = current_milli_time()

for i in range(10000):
    print("a", end="")

endTime1 = current_milli_time()

=====================================

startTime2 = current_milli_time()

for i in range(10000):
    print("ab", end="")

endTime2 = current_milli_time()

=====================================

startTime3 = current_milli_time()

for i in range(10000):
    print("abc", end="")

endTime3 = current_milli_time()

=====================================

print("\nTime(ms) for first case: ", endTime1 - startTime1)
print("Time(ms) for second case: ", endTime2 - startTime2)
print("Time(ms) for second case: ", endTime3 - startTime3)

我们可以看到，在第一种情况下，我们只打印了“a”，在第二种情况下，我们打印了“ab”，在第三种情况下，我们打印了“abc”，时间复杂度随着字符数量的增加而线性增加。

因此，可以说对于每种语言，打印语句都需要 O(lengthOfString) 时间。

Answer 2

这段代码的时间复杂度是 O(N*N)，因为它是一个打印 N 次的循环。我不知道你被告知什么，但打印它的时间复杂度并不比 Java 中的 O(N) 差。

在您的代码中，您将“X”添加到每一行，因此您的打印将是：

X
XX
XXX
XXXX
XXXXX
XXXXXX
.
.
.

所以它的复杂度是作为算术级数计算的，我们得到：

(1+N)*N/2=O(N^2)

要了解该命令的工作原理，您可以在此处或此处阅读：

人们普遍认为 SOP 的性能较差。当我们深入分析时，调用顺序是这样的：println -> print -> write() + newLine()。该序列流是Sun/Oracle JDK 的实现。write() 和 newLine() 都包含一个同步块。同步有一点开销，但更多的是向缓冲区添加字符和打印的成本很高。

当我们运行性能分析时，运行多个SOP并记录时间，执行持续时间成比例增加。当我们打印超过 50 个字符和超过 50,000 行时，性能会下降。

这完全取决于我们使用它的场景。无论情况如何，请勿使用 System.out.println 记录到 stdout。