一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 961|回复: 10
收起左侧

[算法题] 如何计算Backtracking复杂度?

[复制链接] |试试Instant~ |关注本帖
111180611 发表于 2016-10-13 07:39:46 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
例如word break
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
  1. public static boolean wordBreak(String s, Set<String> wordDict) {
  2.         if(s.length() == 0){
  3.             return false;
  4.         }
  5.         return breakup(0, s, wordDict);
  6.     }
  7.    
  8.     public static boolean breakup(int index, String s, Set<String> set){
  9.         if(index >= s.length()){
  10.             return true;
  11.         }
  12.         for(int i = index + 1; i <= s.length(); i++){
  13.             String temp = s.substring(index, i);
  14.             if(set.contains(temp)){
  15.                 if(breakup(i, s, set)){
  16.                     return true;
  17.                 }
  18.             }
  19.         }
  20.         return false;
  21.     }
复制代码
这种做法平均复杂度是多少?最差复杂度是不是O(N!)

评分

1

查看全部评分

stellari 发表于 2016-10-15 02:00:30 | 显示全部楼层
这种类型的backtracking的复杂度其实最好推导:

T(n) = T(1) + T(2) + ... + T(n-2) + T(n-1)

那么

T(n+1) = [ T(1) + T(2) + ... + T(n-2) + T(n-1) ] + T(n)
           = T(n) + T(n) = 2T(n)

也就是n每加1, 时间增加2倍

T(n) = 2T(n-1) = 2 * 2 * T(n-2) = ... 2^k * T(n-k) = ... = 2^(n-1) T(1)

因此T(n) ~ O(2^n)

回复 支持 3 反对 0

使用道具 举报

jerryzhang 发表于 2016-10-13 15:29:13 | 显示全部楼层
查了一下书。backtracking是一种技术,所以不能说backtracking的复杂度是多少。
具体到你这题,你的实现方法负责度是(N!)
用DP的话能降到N^2.

bool wordBreak(string s, unordered_set<string>& wordDict) {
        unordered_set<int> lens;
        if(s.size() == 0)   return true;
        if(wordDict.size() == 0)    return false;
        for(auto w:wordDict){
            lens.emplace(w.size());
        }
        vector<bool> dp(s.size(),false);
        
        for(int i = 0; i < s.size(); i++){
            for(auto len:lens){
                if(i+len<= s.size()){
                    string tmp = s.substr(i, len);
                    if(wordDict.find(tmp) != wordDict.end()){
                        dp[i+len-1] = true;
                    }
                }
            }
            while(dp[i]!= true && i < s.size()) i++;
            if(i == s.size()) break;
        }
        return dp[s.size()-1];
        
    }
回复 支持 1 反对 0

使用道具 举报

jerryzhang 发表于 2016-10-13 07:46:13 | 显示全部楼层
我觉得你的代码不应该从index+1开始吧。
你的这个的复杂度应该是指数了吧。
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-10-13 08:01:02 | 显示全部楼层
我理解,如果n是string长度的话,那么应该是指数,没有到O(n!)。。
回复 支持 反对

使用道具 举报

codeape 发表于 2016-10-13 08:58:21 | 显示全部楼层
本帖最后由 codeape 于 2016-10-13 09:03 编辑

n为s的长度。
符合以下规律T(0) = O(1)
T(1) = O(1) + T(0)
T(2) = O(1) + T(0) + T(1)
T(3) = O(1) + T(0) + T(1) + T(2)
...
T(n) = O(1) + T(0) + T(1) + ... T(n-1)

懒得推导,用python算了下。

  1. def T(n):
  2.     if n == 0:
  3.         return 1
  4.     else:
  5.         s = 1
  6.         for i in range(n):
  7.             s += T(i)
  8.         return s

  9. for i in range(11):
  10.     print("%d\t%d" %(i, T(i)))
复制代码
0          1
1          2
2        4
3        8
4        16
5        32
6        64
7        128
8        256
9        512
10      1024


所以目测是O(2^n)


回复 支持 反对

使用道具 举报

jimmyshie123 发表于 2016-10-13 09:14:42 | 显示全部楼层
leetcode subsets那一类题目复杂度是指数级别的,permutation那一类题目复杂度是O(n!)级别的。
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-10-13 13:06:06 | 显示全部楼层
这个题应该是O(2^n)吧
回复 支持 反对

使用道具 举报

ryuichist 发表于 2016-10-13 23:45:02 | 显示全部楼层
我自己的方法是,先看你有多少个答案,然后计算出每个答案需要多少时间,相乘
回复 支持 反对

使用道具 举报

 楼主| 111180611 发表于 2016-10-14 00:48:47 | 显示全部楼层
codeape 发表于 2016-10-13 08:58
n为s的长度。
符合以下规律T(0) = O(1)
T(1) = O(1) + T(0)

嗯,感谢!我一直以为backtracking这种题不会考复杂度的,昨天看见有面经里有backtracking复杂度。
回复 支持 反对

使用道具 举报

 楼主| 111180611 发表于 2016-10-16 00:32:30 | 显示全部楼层
stellari 发表于 2016-10-15 02:00
这种类型的backtracking的复杂度其实最好推导:

T(n) = T(1) + T(2) + ... + T(n-2) + T(n-1)

简单明了!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 16:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表