字符串时间复杂度

本文关键字：时间复杂度 字符串 | 更新日期: 2023-09-27 18:04:26

public String joinWords(String[] words)
{ 
     String sentence = "";
     for (String w : words)
     {
        sentence = sentence + w;  
     }
     return sentence;
}

假设所有字符串的长度都相同(称之为x)，并且有n个字符串。在每次连接时，都会创建字符串的新副本，并逐个字符地复制两个字符串。第一次迭代需要我们复制x个字符。第二次迭代需要复制2x个字符。第三次迭代需要3x，以此类推。因此总时间是O(x + 2x +…)+ nx)。这就得到了O(xn^2)

1)我不能从书的答案中理解他们如何在第三次迭代中获得3个字符，在第4次迭代中获得4个字符。字符串是不可变的，并且在每个句子变量赋值中都会创建新的字符串对象。然后它应该一个字符一个字符地复制前一个字符串的值和w的值。我又得到了2x个字符。谢谢大家!

字符串时间复杂度

在第一次迭代中，sentence有0个字符，w有x个字符，所以你必须复制x个字符。

在第二次迭代中，sentence有x个字符，w有x个字符，所以你必须复制2*x个字符。

在第三次迭代中，sentence有2*x个字符，w有x个字符，所以你必须复制3*x个字符。

在第4次迭代中，sentence有3*x个字符，w有x个字符，所以你必须复制4*x个字符。

String本身是不可变的，但引用不是。

假设下一个示例:

String s = "1";
s = s + "2";

s将包含值"12"，但字符串"1"不会改变。我们可以在下一个例子中检查它:

String s = "1";
String sBak = s;
s = s + "2";

s = "12"。我们可以检查sBak，以确保"1"没有变化。

现在回到你的样品。假设words = {"first, "second", "third"} .

语句sentence = sentence + w;更新sentence变量。在第一次迭代后，它将是"" + "first"，即"first"。在第二次迭代后，它将等于"first" + "second"，以此类推。

所以sentence每次引用的字符串长度都会增加(每次sentence指向不同的字符串)

相关文章：