java - toString时间和空间复杂度

Question

给定以下方法:

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

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

Answer 1

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

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