Calculate “hard” runtime complexity in recursive solution

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";

Clarification:

Code in fast 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次方。

博客推送