什么时候该算法寻找所有组合的复杂性? [英] What's time complexity of this algorithm for finding all combinations?
本文介绍了什么时候该算法寻找所有组合的复杂性?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
组合
给定两个整数n和k,复位K数的所有可能组合出1 ... N。
例如,如果n = 4和k = 2,一个解决办法是:[ [2,4], [3,4], [2,3] [1,2], [1,3] [1,4], ]
我个人认为,
时间复杂度=为O(n ^ K),n和k输入。
谢谢所有帮助。
最后,时间复杂度= O(C(N,K)* K)= O((N /(K *(N - !!!K)))* K) n和k是输入,
因为,每一次当我们得到一个组合,我们需要复制子列表列表one_rest,这是O(K), 有C(N,K)* K。
C ++
的#include<载体>
使用名字空间std;
一流的解决方案{
上市:
矢量<矢量< INT> >结合(INT N,INT K){
矢量<矢量< INT>>清单;
//输入验证。
如果(N< K)返回目录;
INT开始= 1;
矢量< int的>子列表;
助手(N,K,启动,列表子列表);
返回列表;
}
无效帮手(INT N,INT K,INT开始,
矢量<矢量< INT>> &安培;列表,矢量< INT> &安培;子列表){
//基本情况。
如果(subList.size()== k)的{
矢量< int的> one_rest(子列表);
list.push_back(one_rest);
返回;
}
如果(开始> N)的回报;
的for(int i =启动; I< = N;我++){
//有一个尝试。
subList.push_back(ⅰ);
//做递归。
助手(N,K,I + 1,列表子列表);
//回滚。
subList.pop_back();
}
}
};
解决方案
由于您使用的名单,的push_back
和 pop_back
是 O(1)
操作。此外,你最终产生的有效组合一次。因此,复杂度 0(正选K)
。
Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example, If n = 4 and k = 2, a solution is:[ [2, 4], [3, 4], [2, 3], [1, 2], [1, 3], [1, 4], ]
Personally I think,
time complexity = O(n^k), n and k are input.
Thank you for all help.
Finally, the time complexity = O(C(n,k) * k) = O((n!/(k! * (n - k)!)) * k), n and k is input,
Since, each time when we get a combination, we need copy subList list to one_rest, which is O(k), there is C(n, k) * k.
C++
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int> > combine(int n, int k) {
vector<vector<int>> list;
// Input validation.
if (n < k) return list;
int start = 1;
vector<int> subList;
helper(n, k, start, list, subList);
return list;
}
void helper(int n, int k, int start,
vector<vector<int>> &list, vector<int> &subList) {
// Base case.
if (subList.size() == k) {
vector<int> one_rest(subList);
list.push_back(one_rest);
return;
}
if (start > n) return;
for (int i = start; i <= n; i ++) {
// Have a try.
subList.push_back(i);
// Do recursion.
helper(n, k, i + 1, list, subList);
// Roll back.
subList.pop_back();
}
}
};
解决方案
Since you are using lists, push_back
and pop_back
are O(1)
operations. Also, you end up generating a valid combination exactly once. Thus, the complexity is O(n choose k)
.
这篇关于什么时候该算法寻找所有组合的复杂性?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文