java - Java中字符串重复追加的大O

Question

我有一个函数可以获取一个字符串作为原始字符串的重复。我想知道如果我使用 StringBuilder 追加，该函数的 Big O 是什么？是 O(nl) 吗:n 是重复次数，l 是原始字符串的长度？

public String getRepetition(String originalStr, Integer n){
    StringBuilder str = new StringBuilder();
    for(int i = 0; i < n; i++)
        str.append(originalStr);
    return str.toString();
}

与下面的方法相比，哪一种更好？

public String getRepetition(String originalStr, Integer n){
    String str = "";
    for(int i = 0; i < n; i++)
        str += originalStr;
    return originalStr;
}

Answer 1

我不确定为什么其他三个答案都说这两段代码都是 O(n) 。假设 originalStr 不是 ""，第一个是 O(n)，另一个是 O(n^2)! (这是一个感叹号，而不是阶乘。)他们在 Java 学校的第一天教授这个。 C 程序员得到“在 for 循环的条件下不要使用 strlen”； Java 程序员明白这一点。

String str = "";
for(int i = 0; i < n; i++)
    str += originalStr;

每次循环str都会变得更长。它是i * orinalStr.length()。创建一个新的String(假设没有狂野编译器优化)，每次所花费的时间大致与i成正比。

编辑:通常我们会忽略原始字符串的长度。但是，是的，它当然是比例的，所以 O(nstrlen(originalStr)) 和 O(nn*strlen(originalStr)) 。按照惯例，这是单独处理的。

如果我们重写代码而不使用String抽象，也许会更清晰。

public static char[] getRepetition(char[] originalStr, int n) {
    char[] str = {};
    for (int i = 0; i < n; ++i) {
        assert str.length == i * originalStr.length;
        char[] newStr = new char[str.length + originalStr.length];
        for (int j=0; j<str.length; ++j) {
            newStr[j] = str[j];
        }
        for (int j=0; j<originalStr.length; ++j) {
            newStr[str.length+j] = originalStr[j];
        }
        str = newStr;
    }
    return str;
}

(一如既往，我懒得编译代码。在核 react 堆中使用不安全。)

为了搞笑，让我们对第一个实现进行抽象。

public static char[] getRepetition(char[] originalStr, int n) {
    char[] str = new char[16];
    int strLen = 0;
    for (int i = 0; i < n; ++i) {
        assert strLen == i * originalStr.length;
        // ensureCapacity
        if (str.length < strLen + originalStr.length) {
            // The size at least doubles, 
            //   so this happens increasing less often.
            // It wont happen again for approximately
            //   the same number of iterations
            //   as have already happened!
            char[] newStr = new char[Math.min(
                str.length + originalStr.length, // first time safe
                str.length*2 + 2                 // *2 !
            )];
            for (int j=0; j<strLen; ++j) {
                newStr[j] = str[j];
            }
            str = newStr;
        }
        // actual append
        for (int j=0; j<originalStr.length; ++j) {
            str[strLen++] = originalStr[j];
        }
    }
    // toString
    char[] newStr = new char[strLen];
    for (int i=0; j<newStr.length; ++i) {
         newStr[i] = str[j];
    }
    return newStr;
}