string - 获取没有字符的字符串的所有子字符串的时间复杂度是多少？

Question

这样做的目的是找到删除单个字符的字符串的所有子字符串。

例如对于字符串 abc，我们需要得到[abc, ac, ab, bc, a, c, b].

假设我们为此使用递归，时间复杂度是多少？我不是在寻求解决方案，我只是想知道哪个是时间复杂度以及为什么。

标签： stringalgorithmrecursion

Answer 1

复杂度是k从0到n的二项式系数(n, k)的总和。这等于2^n。

你可以在这里找到证明：http: //mathworld.wolfram.com/BinomialSums.html