string - 字符串子序列递归的时间复杂度

如何计算下面算法的时间复杂度？有人能简单地向我解释一下吗：

public static void print(String prefix, String remaining, int k) {
    if (k == 0) {
        StdOut.println(prefix);
        return;
    }
    if (remaining.length() == 0) return;
    print(prefix + remaining.charAt(0), remaining.substring(1), k-1);
    print(prefix, remaining.substring(1), k);
}


public static void main(String[] args) {
    String s = "abcdef";
    int k = 3;
    print("", s, k);
}

最佳答案

假设m是prefix的长度，n是remaining的长度然后给出了复杂性。
T（m，n，k）=Θ（m+n）+T（m+1，n-1，k-1）+T（m，n-1，k）。
Θ（m+n）项源于

prefix + remaining.charAt(0), remaining.substring(1)

一般来说，这需要分别创建两个长度约为m和n的新字符串（这在不同的实现中可能有所不同）。
除此之外，除了一些非常简单的边界外，很难求解（至少对我来说是这样）例如，很明显，复杂度至少在前缀和k的最小长度上是指数的，因为
t（m，n，k）≥2t（m，n-1，k-1）t（m，n，k）=Ω（2min（n，k））。