一亩三分地论坛

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

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

[算法题] Combination sum 1 and 2

[复制链接] |试试Instant~ |关注本帖
douya 发表于 2015-7-6 06:20:11 | 显示全部楼层 |阅读模式

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

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

x
为什么time complexity是 n!? 我觉得是2^n 啊? 求教!


public class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> item = new ArrayList<Integer>();
        if(candidates==null || candidates.length==0){
            return result;
        }
        Arrays.sort(candidates);
        helper(candidates,target,0,0,result,item);
        return result;
    }

    private void helper(int[] cand, int target, int sum, int index, List<List<Integer>> result, List<Integer> item){
        if(sum==target){
            result.add(new ArrayList<Integer>(item));
            return;
        }
        if(sum>target){
            return;
        }
        for(int i=index;i<cand.length;i++){
            if(i>0 && cand==cand[i-1]) continue;
            item.add(cand);
            helper(cand,target,sum+cand,i,result,item);
            item.remove(item.size()-1);
        }

    }
}



stellari 发表于 2015-7-6 14:26:58 | 显示全部楼层
本帖最后由 stellari 于 2015-7-6 14:28 编辑

这样吧,我给一个估计。不是严格证明,但是应该差不多:
假设target = T, A中的元素是A0, A1, A2, A3, ..., AN,其中总有A0 = 1(为了保证A1~AN的任何一个和<K的组合都能够成立).
那么对任一N维向量k = (k1, k2, ..., kN)
如果其满足
ki > 0 且
k1*A1 + k2*A2 + ... + KN*AN <= T
那么k就是combination sum的一组解。

而k1*A1 + k2*A2 + ... + KN*AN <= T在k所在的向量空间内定义了一个N维的simplex(即三角形,四面体的多维情况)。比如N = 3, A = [1, 2, 3], T = 100. 那么1*k1 + 2*k2 + 3*k3 <= 100在三维空间中定义了一个四面体,该四面体和3坐标轴分别交于(100, 0, 0), (0, 100/2, 0), (0, 0, 100/3)。推广至N维情况,交点则分别为v1 = (T/A1, 0, 0, ... 0), v2= T(0, T/A2, 0 ,.... 0), ... v3 = T(0, ... , T/AN)。它们共同构成了一个对角矩阵:
S = [v1' v2' ... vN'] = T*I*(1./A)
这样的一个simplex的体积有公式得:
1/N! * det|T*I*(1./A)|
其中det|... |表示行列式。

而 det|T*I*(1./A)| = T^N/prod(A) , 即T的N次方除以A中所有元素乘积的倒数,所以simplex的体积为

T^N/(N!*prod(A))

而对于较大的simplex,其中的整数坐标点的个数在数值上近似与其体积相等。因此该程序的时间复杂度应该近似为

f(N, T) ~ T^N / (N! * prod(A))

如果当T很大,而A中元素都很小时,可以看做O(T^N)。
回复 支持 2 反对 0

使用道具 举报

zhuli19901106 发表于 2015-7-9 13:38:36 | 显示全部楼层
pyx115 发表于 2015-7-6 06:45
LZ想说是 N^2? N! 就是 N^2 啊

神回复啊神回复~
回复 支持 1 反对 0

使用道具 举报

pyx115 发表于 2015-7-6 06:45:06 | 显示全部楼层
LZ想说是 N^2? N! 就是 N^2 啊
回复 支持 反对

使用道具 举报

 楼主| douya 发表于 2015-7-6 07:49:15 | 显示全部楼层
pyx115 发表于 2015-7-6 06:45
LZ想说是 N^2? N! 就是 N^2 啊

我觉得是2^n啊
感觉是T(n) = T(n-1) + T(n-2)+....T(1)
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-6 09:14:43 | 显示全部楼层
就是O(2^N),准确说是O(N*2^N)。见下帖讨论:

http://www.1point3acres.com/bbs/thread-117602-1-1.html
回复 支持 反对

使用道具 举报

 楼主| douya 发表于 2015-7-6 11:55:50 | 显示全部楼层
stellari 发表于 2015-7-6 09:14
就是O(2^N),准确说是O(N*2^N)。见下帖讨论:

http://www.1point3acres.com/bbs/thread-117602-1-1.html

您好,
多谢回复!
我想问的是combination sum I, II. 不是combinations。 不过应该都是2^n 吧。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-6 12:58:38 | 显示全部楼层
本帖最后由 stellari 于 2015-7-6 13:04 编辑
douya 发表于 2015-7-6 11:55
您好,
多谢回复!
我想问的是combination sum I, II. 不是combinations。 不过应该都是2^n 吧。

Oops,不好意思,看错了题目。如果是这两道题的话,时间复杂度肯定不仅仅是数组长度N的函数,而是N, K(K为Target)的二维函数。设想[1,2,3], 10和[1,2,3], 1000这两个例子。后者的搜索时间远大于前者。如果数组中包含的数据恰为[1~N]这N个数,且K大于N时,可以证明时间复杂度应在O(K^N)水平。但是K^N只是个比较松的上界。至于是否有更逼近的上界暂时我还证不出来。
回复 支持 反对

使用道具 举报

 楼主| douya 发表于 2015-7-7 09:05:05 | 显示全部楼层
stellari 发表于 2015-7-6 14:26
这样吧,我给一个估计。不是严格证明,但是应该差不多:
假设target = T, A中的元素是A0, A1, A2, A3, ... ...

我再看看这个证明。
回答这么细,
非常感谢您啊!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 22:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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