江苏龙网

  1. 主页 > 生活百科 > >

一文学会排列组合 排列组合公式( 四 )


快排的时光庞杂度为 O(nlogn)，而 next_permutation 由于要盘算 n! 次，且依据以上剖析我们已经知道了 next_permutation 的时光庞杂度是 O(nlogn), 所以整体的时光庞杂度是
O(nlog) + O(n! * nlogn) = O(n! * nlogn) 。
看起来字典序法比递归的时光庞杂度更高,所以我们应当应用偏向于应用递归吗？这里注意: 递归的实现是通过调用函数本身，函数调用的时候，每次调用时要做地址保留，参数传递等，这是通过一个递归工作栈实现的 。具体是每次调用函数本身要保留的内容包含：局部变量、形参、调用函数地址、返回值 。那么，如果递归调用N次，就要分配N局部变量、N形参、N调用函数地址、N返回值，这势必是影响效力的，同时，这也是内存溢出的原因，因为积聚了大批的中间变量无法释放 。
所以在时光庞杂度差不多的情形下，优化选择非递归的实现方法
一文学会排列组合
什么是组合
看完了排列，我们来看看组合，首先我们还是先看看组合的定义
组合（combination）是一个数学名词 。一般地，从n个不同的元素中，任取m（m≤n）个元素为一组，叫作从n个不同元素中取出m个元素的一个组合 。我们把有关求组合的个数的问题叫作组合问题 。
假设有数字1, 2, 3, 4, 要从中选择 2 个元素，共有多少种组合呢
一文学会排列组合
共有 6 种
排列与组合最重要的差别就是排列是有序的，而组合是无序的，12 和 21 对组合来说是一样的
现在我们来看看如果从 n 个元素中选出 m 的组合共有几种，之前详细地讲授了如何用递归解排列，信任大家应当对组合怎么应用递归应当有一个比拟清楚的思路 。
我们一起来看看，假设要从 n 选 m 的组合的解题思路
一文学会排列组合
这里须要注意的是相对于全排列的每个元素都能参与排列不同，组合中的每个元素有两种状况，选中或未选中,所以形成递归分两种情形 。
如果第一个元素选中，则要从之后的 n-1 个元素中选择 m-1 个元素
一文学会排列组合
如果第一个元素未被选中，则须要从之后的 n-1 个元素选择 m 个元素
一文学会排列组合
递归条件既然找到了，接下来我们就按递归四步曲来解下组合 。
1、定义函数的功效定义以下函数为从数组 arr 中第 k 个地位开端取 m 个元素（如下的 COMBINATION_CNT）
public static final int COMBINATION_CNT = 5; // 组合中须要被选中的个数
public static void combination(int[] arr, int k, int[] select) {
}
这里我们额外引入了一个 select 数组，这个数组里的元素如果为1，则代表相应地位的元素被选中了，如果为 0 代表未选中
一文学会排列组合
如图示，以上表现 arr 的第 2，3 元素被选中作为组合
2、寻找递推公式显然递推公式为
combination(arr, k,m) = (选中 k 地位的元素 +combination(arr, k+1) ) + (不选中 k 地位的元素 +combination(arr, k+1) )
那么终止条件呢，有两个
一个是被选中的元素已经等于我们要选择的组合个数了
一个是 k （开端选取的数组索引） 超越数组规模了 。
3、将第二步的递推公式用代码表现出来弥补到步骤 1 定义的函数中，弥补后的函数如下
 public static final int COMBINATION_CNT = 5; // 组合中须要被选中的个数
public static void combination(int[] arr, int k, int[] select) {
// 终止条件1：开端选取的数组索引 超越数组规模了
if (k >= arr.length) {
return;
}int selectNum = selectedNum(select);
// 终止条件2：选中的元素已经等于我们要选择的数组个数了
if (selectNum == COMBINATION_CNT) {
for (int j = 0; j < select.length; j++) {
if (select[j] == 1) {
System.out.print(arr[j]);
}}System.out.print("\n");
} else {
// 第 k 位被选中
select[k] = 1;
combination(arr, k+1, select);
// 第 k 位未被选中
select[k] = 0;
// 则从第 k+1 位选择 COMBINATION_CNT - selectNum 个元素
combination(arr, k+1, select);
}}public static void main(String[] args) {int arr = {1,2,3,4,5,6,7,8,9};
int select = {0,0,0,0,0,0,0,0,0};
// 一开端从 0 开端选 组合数
combination(arr, 0, select);
}
4、求时光/空间庞杂度空间庞杂度：由于我们用了一个帮助数组 select, 所以空间庞杂度是 O(n)时光庞杂度：可以看到 f(n) = 2f(n-1)，所以时光庞杂度是O(2^n),显然是指数级别的
画外音：大家可以斟酌一下怎么优化，提醒:每种元素只有选中和被选中的状况，是不是对应了二进制的 0 和 1，可以斟酌用位运算


推荐阅读


上一篇：教你把二、十六进制数转换成十进制数 十六进制转十进制

下一篇：同比增长和环比增长的区别 环比和同比是什么意思