[八我司] Expedia一年半遊:这是一個特別適合養老待退的地方

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 2556|回复: 10
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
111180611 发表于 2016-10-13 07:39:46 | 显示全部楼层 |阅读模式
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】

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

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

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大米 +2 收起 理由
williamflea + 2 很有用的信息!

查看全部评分


上一篇:三番刷题组队
下一篇:问一题google foobar的题
我的人缘0
stellari 发表于 2016-10-15 02:00:30 | 显示全部楼层
  此人我要顶:
 
100% (3) 【我投】
  此人我要踩:
 
0% (0) 【我投】
这种类型的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

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
jerryzhang 发表于 2016-10-13 15:29:13 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
查了一下书。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

使用道具 举报

我的人缘0
jerryzhang 发表于 2016-10-13 07:46:13 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
我觉得你的代码不应该从index+1开始吧。
你的这个的复杂度应该是指数了吧。
回复 支持 反对

使用道具 举报

我的人缘0
zpinthehouse 发表于 2016-10-13 08:01:02 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
我理解,如果n是string长度的话,那么应该是指数,没有到O(n!)。。
回复 支持 反对

使用道具 举报

我的人缘0
codeape 发表于 2016-10-13 08:58:21 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
本帖最后由 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)


回复 支持 反对

使用道具 举报

我的人缘0
jimmyshie123 发表于 2016-10-13 09:14:42 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
leetcode subsets那一类题目复杂度是指数级别的,permutation那一类题目复杂度是O(n!)级别的。
回复 支持 反对

使用道具 举报

我的人缘0
jy_121 发表于 2016-10-13 13:06:06 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这个题应该是O(2^n)吧
回复 支持 反对

使用道具 举报

我的人缘0
ryuichist 发表于 2016-10-13 23:45:02 | 显示全部楼层
  此人我要顶:
 
91% (11) 【我投】
  此人我要踩:
 
9% (1) 【我投】
我自己的方法是,先看你有多少个答案,然后计算出每个答案需要多少时间,相乘
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 111180611 发表于 2016-10-14 00:48:47 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
codeape 发表于 2016-10-13 08:58
n为s的长度。
符合以下规律T(0) = O(1)
T(1) = O(1) + T(0)

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

使用道具 举报

我的人缘0
 楼主| 111180611 发表于 2016-10-16 00:32:30 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
stellari 发表于 2016-10-15 02:00
这种类型的backtracking的复杂度其实最好推导:

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

简单明了!
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-6-19 14:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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