java - 算法，大 O 表示法 : Is this function O(n^2) ? 还是 O(n)？

Question

这是算法书籍“Java 中的数据结构和算法，第 6 版”中的代码。作者:Michael T. GoodRich、Roberto Tamassia 和 Michael H. 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，依此类推，直到我们到达最后一个长度为 string 的字符串 n。”

但是，我不明白，这段代码怎么会有 O(n^2)，因为无论 n 的值如何(不包括 j < n 和 j++)，它的原始操作数每次迭代都会加倍。无论 n 的值如何，语句 answer += c 每次迭代都需要两个原始操作，因此我认为这个函数的等式应该是 4n + 3。(每个循环操作 j

或者，是这句话，“就效率而言，这种解释的问题在于，作为连接的结果创建一个新字符串，需要的时间与结果的长度成正比string.,"只是简单地说，无论函数中使用的原始操作的数量如何，作为连接的结果创建一个新字符串需要与其长度成比例的时间？所以原始操作的数量对函数的运行时间没有太大影响，因为串联字符串赋值运算符的运行时间的内置代码在 O(n^2) 中运行。

这个函数怎么可能是 O(n^2)？

感谢您的支持。

Answer 1

在循环的每次迭代中，语句 answer += c; 必须将字符串 answer 中的每个字符复制到一个新字符串中。

例如n = 5, c = '5'

• 第一个循环:answer 是一个空字符串，但它仍然必须创建一个新字符串。有一个附加第一个 '5' 的操作，answer 现在是 "5"。
• 第二个循环:answer 现在将指向一个新字符串，第一个 '5' 被复制到另一个 '5' 附加，使 "55"。不仅创建了一个新的 String，还从之前的字符串中复制了一个字符 '5' 并附加了另一个 '5'。附加了两个字符。
• “n”循环:answer 现在将指向一个新字符串，其中 n - 1 '5' 个字符复制到新字符串，并附加一个附加的 '5' 字符，以构成一个包含 n 5 的字符串。

复制的字符数为 1 + 2 + ... + n = n(n + 1)/2。这是 O(n²)。

在 Java 的循环中构造这样的字符串的有效方法是使用 StringBuilder，使用一个可变的对象并且不需要每次复制一个字符时复制所有字符附加在每个循环中。使用 StringBuilder 的成本为 O(n)。