How to calculate “hard” runtime complexity in recursive solution?

包子IT面试培训 助你拿到理想的offer!

在技术面试中，准确说出一个解法的runtime complexity（算法时间复杂度）是一个非常重要的点。考虑到对于算法时间复杂度的理解是CS领域的基础，因此这类问题，回答对了往往不加分，但是回答错误往往是致命的，因此大家不能掉以轻心。

Note: 本篇只讨论算法的时间复杂度，不涉及算法的空间复杂度。:)

对于基本的算法复杂度分析，Big O notation是必须要掌握的，详情请看wikipedia相关资料：http://en.wikipedia.org/wiki/Big_O_notation 。 简单的说，Big O描述了当输入(input)的复杂度线性增长时，一个算法的计算时间复杂度的增长变化。举个例子，如果我们说一个算法的是时间复杂度是O(n)，那么意味着当该算法的输入线形增长时，其计算时间也成线性增长。

『简单的时间复杂度计算』

大部分非递归算法的时间复杂度计算比较简单，一句话简单表述，就是数有多少层嵌套循环即可，（每个循环的次数和算法的输入n相关）。比如一个问题描述『求n个int数中的最大数』，那么解法中需要用一次循环来遍历所有input（即n个数），然后返回结果。由于只需要一层循环，那么该算法时间复杂度为O(n).

『相对复杂的时间复杂度计算』

当一个算法中既包含循环(loop)又包涵递归(recursive)的时候，算时间复杂度可能需要动动脑筋。这部分也是本章重点。:)

用最近的一道高频题做例子：

Problem:

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.  Return one such possible sentences.

s = "catsanddog", dict = ["cat", "cats", "and", "dog"], return “cats and dog"；

(Leetcode word break II 简化版)

Clarification

Q: What to return if s can’t be splitted into words in dict? A: Return NULL;

Q: What if there are multiple ways of splitting s? A: Return one split solution is fine;

Q: What if S is null/empty string? A: Return NULL;

So on and so forth..

Code in first pass:

 public String wordBreak(String s, Set<String> dict) {

   if (s == null || s.isEmpty()) {

     return s;

   }

   List<String> solution = new ArrayList<String>();

   boolean ret = wordBreakHelper(s, dict, solution);

   if (!ret) {

     return null;

   }

  

   //from apache commons lang

   return StringUtils.join(solution, " ");

 }

 

 private boolean wordBreakHelper(String s, Set<String> dict, List<String> solution) {

   if (dict.contains(s)) {

     solution.add(s);

     return true;

   }

   for(int index = 1; index < s.length(); ++index) {

       String left = s.substring(0, index);

       if (dict.contains(left)) {

         solution.add(left);

         boolean ret = wordBreakHelper(s.substring(index), dict, solution);

         if (ret) {

           return ret;

         } else {

           solution.remove(solution.size() - 1);

         }

       }

    }

    return false;

 }

这样的解法看起来一目了然，对于每一个字符串，分成左右子字符串，查左子串、递归右子串（想想为什么不需要递归左子串）。

那么这个算法的时间复杂度是多少呢？

这个复杂度的计算并非那么容易一眼看出，因为解法中的循环内有递归，而每一个递归中又存在循环。所以数嵌套循环数的方法并不好用。因此我们拿一个具体的例子来看：

假设字符串s是abcde; 那么算法变化如下：

当index = 1, 字符串分为左串a和右串bcde，如果a不在字典中，那么这个拆分不成立，情况简化；如果a恰好在字典中，那么算法有两种选择，一种选择是将a放入结果集，然后递归bcde，另一种是不选择a作为完整单词，而是作为单词的一部分去试探下一个index。

当index = 2, 由于index = 1时产生了两种情况：a bcde 和 abcde。

对于a bcde的情况，由于算法递归bcde，和index = 1的情况类似，如果b在字典中，那么会演化出两种情况：a b cde; a bcde;

对于abcde的情况，如果ab在字典中，那么会演化出两种情况：ab cde; abcde;

写到这里，大家应该看得出来，对于每一个index上的字母，是否选择该字母作为单词结束的决定会产生两种可能，而且是层层叠加。因此该算法的复杂度就是2的n次方。

Code in second pass:

上面的写法虽然思路简单，但是不可避免的进行了很多重复运算。比如cde这个单词至少会被a b cde 和ab cde这两种拆分方法共同计算，如果我们能利用一个额外的集合记录之前的计算结果，那么算法的复杂度会大大下降。

修改代码：

 private boolean wordBreakHelper(String s, Set<String> dict, Set<String> unsplitableSet, List<String> solution) {

   if (dict.contains(s)) {

     solution.add(s);

     return true;

   }

   if (unsplitableSet.contains(s)) {

     return false;

   }

   for(int index = 1; index < s.length(); ++index) {

       String left = s.substring(0, index);

       if (dict.contains(left)) {

         solution.add(left);

         boolean ret = wordBreakHelper(s.substring(index), dict, unsplitableSet, solution);

         if (ret) {

           return ret;

         } else {

           solution.remove(solution.size() - 1);

         }

       }

    }

    unsplitableSet.add(s);

    return false;

 }

既然上面的算法避免了相同子串的重复计算，那么以上这个算法的时间复杂度是多少呢？

考虑到所有重复计算已经被排除，那么我们不防穷举所有可能的计算尝试，同样以abcde为例：

以a开头的尝试：a, ab, abc, abcd, abcde,

以b开头的尝试：b, bc, bcd, bcde,
以c开头的尝试：c, cd, cde,  

…

显然所有的计算尝试是n平方的复杂度（n位字符串长度），考虑到所有的尝试只计算一次（算法中的unsplitableSet起到的作用），因此上面的时间复杂度位n的2次方。