9

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

例如，以下关于 N 的时间复杂度是多少？

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

感谢您帮助新人！

4

6 回答 6

4

这段代码的时间复杂度是 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 来记录到标准输出。

于 2013-09-08T05:17:12.437 回答
4

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

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) 时间。

于 2021-04-08T07:55:27.717 回答
2

时间复杂度告诉你每增加一个输入大小，你的算法需要做多少工作，给定或取一些常数系数。

所以 O(2 N) 的上限复杂度等于复杂度 O(23587 N) 因为这里找到的实际定义

http://en.wikipedia.org/wiki/Big_O_notation

声明系数可以是任何数字，无论多大，只要它相对于输入的大小是固定的。

因为你没有在循环中使用'N'，你只是在一个字符串上添加一个字符，每次迭代的工作量等于你有多少次迭代-> O(N)

如果你有 "stringy += stringy;" 取而代之的是 O(N^2) 因为每次迭代都会使您必须做的工作量增加一倍

* *注意

我假设 system.out.print 是一个原子语句，即它将所有字符打印为一个动作..如果它单独打印每个字符，那么它的 O(N^2)....

于 2013-09-08T05:24:23.263 回答
1

这段代码的复杂度是O(n^2). 它迭代循环 N 次，并且因为System.out.println必须打印每个字符，每次迭代打印 0 到 N 个字符，平均 N/2，你删除常数，N*N = N^2。以同样的方式，添加到字符串将导致整个字符串被复制（字符串在 Java 中是不可变的，因此任何更改都意味着您必须将整个字符串复制到新字符串中）。这是另一个线性操作。因此，您n * (n/2 + n/2)仍然处于二次阶 - O(n^2)。

String stringy = "";
while(stringy.length() < N) { // will iterate N times
    System.out.println(stringy); // has to print N letters
    stringy += "X"; // has to copy N letters into a new string
}
于 2013-09-08T05:21:37.803 回答
1

可以在这里找到一个很好的答案： http ://www.quora.com/What-exactly-is-the-time-complexity-for-System-out-println-in-Java-O-1-or-ON

主要思想是打印字符串实际上是将其复制到标准输出 - 我们知道字符串的副本是 o(n)。

第二部分说你可以尝试打印很多次： - 一个字符 - 一个非常大的字符串 你会看到时差！！（如果打印是 o(1) 你不会）

于 2015-06-05T13:23:07.387 回答
0

命令的时间复杂度System.out.println(stringy);？？？

您基本上是指上面代码片段的时间复杂度。看，时间复杂度与一种特定的代码或语言没有特别的关系，它基本上意味着理论上这行代码将花费多少时间。这通常取决于两三件事：

  • 输入的大小
  • 多项式的次数（在求解多项式方程的情况下）

现在在这部分代码中：

String stringy = "";
while(stringy.length() < N) {// the loop will execute in order of N times 
    System.out.println(stringy);//println will execute in order of N times too as in printing each character 
    stringy += "X";
}

这显然取决于输入的大小，当然也就是字符串的长度。首先，while循环执行的时间比N少一点（因为它的条件stringy.length() < N 会使<=它贯穿字符串的全长），我们可以按N的顺序说，打印字符串将按N的顺序完成，所以整体代码的运行时间为O(N^2)

于 2013-09-08T05:17:31.893 回答