这是一本算法书的代码，“Java中的数据结构和算法，第6版”，作者是MichaelT.GoodRich、RobertoTamassia和MichaelH.Goldwasser
public static String repeat1(char c, int n)
{
String answer = "";
for(int j=0; j < n; j++)
{
answer += c;
}
return answer;
}
作者认为，该算法的大o符号是o（n^2），原因如下：
“命令answer+=c是answer=（answer+c）的简写。这个
命令不会导致将新字符添加到现有字符串中。
相反，它生成了一个新字符串，其中包含所需的
字符，然后重新分配变量answer，以引用新的
弦就效率而言，这种解释的问题在于
作为连接的结果创建新字符串需要时间
它与结果字符串的长度成比例第一次
通过这个循环，结果的长度为1，第二次通过循环
结果的长度是2，依此类推，直到我们到达最后的长度字符串
“不。”
但是，我不明白，这段代码怎么可能有o（n^2），因为它的基本操作数只是每次迭代的两倍，而不管n的值是多少（不包括j语句answer+=c每次迭代都需要两个基元操作，而不考虑n的值，因此我认为这个函数的方程应该是4n+3（每个回路运行J
或者，是这样一句话，“就效率而言，这种解释的问题是，由于连接而创建一个新字符串，需要与结果字符串的长度成比例的时间。”“简单地说，创建一个新字符串作为连接的结果需要与其长度成比例的时间，而不管函数中使用的基本操作的数量是多少？因此，基元操作的数量对函数的运行时间没有太大的影响，因为连接字符串赋值运算符的运行时间的内置代码在O（n^2）中运行。
这个函数怎么可能是o（n^2）？
谢谢你的支持。
最佳答案
在循环的每次迭代过程中，语句answer += c;必须将字符串answer中已经存在的每个字符复制到一个新字符串中。
例如n=5，c='5'
第一个循环：answer是空字符串，但它仍必须创建新字符串。有一个操作附加第一个'5'，现在answer是"5"。
第二个循环：answer现在将指向一个新字符串，第一个'5'被复制到一个新字符串中，并附加另一个'5'，以生成"55"。不仅创建了一个新的String，还从前一个字符串复制了一个'5'，并附加了另一个'5'附加两个字符。
“n”th循环：answer现在将指向一个新字符串，其中n-1'5'个字符复制到一个新字符串，并附加一个'5'个字符，以生成一个包含n 5s的字符串。
复制的字符数为1+2+…+n=n（n+1）/2。这是o（n2）。
在java中，在循环中构造这样的字符串的有效方法是使用StringBuilder，使用一个可变的对象，并且不需要每次在每个循环中追加一个字符时复制所有字符。使用aStringBuilder的成本为o（n）。
关于java - 算法，大O表示法:这个函数是O(n ^ 2)吗？或O(n)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/51598406/