这是正确的时间复杂度吗？

Question

我这样做是为了解决其中一个 leetcode 问题，但我不确定我的算法的复杂度是多少。

public String countAndSay(int n) {
        if (n == 1) return "1";
        String pre = countAndSay(n-1);
        char[] prev = pre.toCharArray();
        int len = prev.length;
        if (len == 1 && prev[0] == '1') return "11";
        int idx = 1;
        int rep = 1;
        String res = "";
        while (idx <= len) {
            if (idx == len) {
                res += (Integer.toString(rep) + prev[idx-1]);
                break;
            }
            if (prev[idx-1] == prev[idx]) rep++;
            else {
                res += (Integer.toString(rep) + prev[idx-1]);
                rep = 1;
            }
            idx++;
        }
        return res;
    }

由于递归n次，循环复杂度为O(n)，我感觉应该是O(n^2)。那是对的吗？如果不是，能否解释一下原因？

Answer 1

这里有一些事实：

该方法在输入时递归调用自身 n-1。
该方法生成的序列称为 look-and-say sequence。
结果字符串的长度以λ为底呈指数增长，其中λ=1.303577269034...为Conway's constant，所以长度为O(λ^n).
循环是字符串长度的二次方（因为重复的字符串连接），所以我们有 O((λ^n)^2) = O((λ^2)^n) 循环。

由此可以推导出如下递归关系：

T(0) = 1
T(n) = T(n-1) + O((λ^2)^n)

此关系的渐近行为由

给出

T(n) ∈ Θ((λ^2)^n) = Θ(1.6993^n)

如果你使用 StringBuilder 而不是进行邪恶的重复字符串连接，你可以将它降低到 Θ(λ^n) 这对于这个问题也是渐近最优的。

这是正确的时间复杂度吗？

Is this correct time complexity?

performance

time

big-o

time-complexity

code-complexity