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

Question

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

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);
}

Answer 1

假设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) ≥ 2 T(m, n - 1, k - 1) ↠ T(m, n, k) = Ω(2^{min(n, k)} )。