toString 时间和 space 复杂度

Question

给定以下方法：

public String toString()
{
    if (_head == null)
        return "";
    String S="";
    WordNode currentNode = _head;
    while (currentNode != null)
    {
       S+=currentNode.getWord()+" ";
       currentNode = currentNode.getNext();
    }   
    return S;

}

什么是时间和 space 复杂性？在 Java 中，String 是不可变对象。它如何影响复杂性？谢谢

Answer 1

时间复杂度为 O(n)，其中 n 是节点数，因为您对每个节点迭代一次。 Space 复杂度实际上是 O(n*m)，其中 n 是节点数，m 是您将创建的最大字符串的长度（这是包含所有单词的最后一个字符串）。这是因为您创建了 n 个字符串，并且在 java 中创建的字符串的内存使用量与字符串中的字符数成正比（在您的情况下是最大 m）。如果您想准确查看创建字符串使用了多少内存，请参阅此 link：http://www.javamex.com/tutorials/memory/string_memory_usage.shtml.

顺便说一句，您实际上并不需要在函数的开头进行 if 检查，因为如果 head 为 null，您的 while 循环将不会进行任何迭代，并且您将 return 无论如何都是一个空字符串。去掉这个条件将使你的时间性能提高一个常数因子（但时间复杂度当然是一样的）。

Answer 2

时间复杂度为O(L*N)，其中N是节点数，L是结果字符串的长度：

如果除第一个节点以外的所有节点都包含一个长度为 1 的字符串，并且第一个节点包含一个字符串 L-2*(N-1)-1。然后存储在 S 中的字符串在循环迭代中的长度为

L-2*(N-1)
L-2*(N-2)
L-2*(N-3)
...
L

这些值的总和在 O(L*N) 中。由于分配字符串所花费的时间与字符串大小成正比，因此该算法的时间复杂度为 O(N*L).

space 复杂度为 O(L)，因为存储在 S 中的字符串的长度在 O(L) 中，并且垃圾收集器可以回收先前迭代的中间结果作为一旦 S 被覆盖。

您可以使用 StringBuilder.

将其改进为 space 和时间复杂度 O(L)

public String toString()
{
    if (_head == null)
        return "";
    StringBuilder S=new StringBuilder();
    WordNode currentNode = _head;
    while (currentNode != null)
    {
       S.append(currentNode.getWord()).append(" ");
       currentNode = currentNode.getNext();
    }   
    return S.toString();

}

Answer 3

每个迭代 n 项的循环的时间复杂度为 O(n)。当你在另一个循环中嵌套循环时

while(...) {
   while(...) {
    ...
   }
}

它变成了 O(n^2) 等等。

由于您只使用一个循环，因此您的方法时间复杂度为 O(n)。

toString 时间和 space 复杂度

toString time and space complexity

java

time-complexity

tostring

space-complexity