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是不可变的对象。它如何影响复杂性？谢谢。

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循环将不会进行任何迭代，并且无论如何您都将返回一个空字符串。排除此条件将使您的时间性能提高一个常数（但是时间复杂度当然会相同）。