网站信息做参考文献,射阳做企业网站多少钱,中企动力做的家具行业网站,品牌网页设计公司子集树#xff1a;O(2^n)
一个序列的所有子集为2^n#xff0c;即可看成具有2^n个叶节点的满二叉树 int backtrack(int k) //k表示扩展结点在解空间树中所处的层次
{if(kn) //n标识问题的规模output(x); //x是存放当前解的一维数组if(constraint(k)…子集树O(2^n)
一个序列的所有子集为2^n即可看成具有2^n个叶节点的满二叉树 int backtrack(int k) //k表示扩展结点在解空间树中所处的层次
{if(kn) //n标识问题的规模output(x); //x是存放当前解的一维数组if(constraint(k)) //约束函数{ //做相关标识backtrack(k1)//做相关标识的反操作 } if(bound(k)) //限定函数{//做相关标识backtrack(k1)//做相关标识的反操作 }} 常用于解空间为子集树的常见问题 10-1背包问题 2子集和问题 3装载问题 4最大团问题。 排序树O(n!) int backtrack(int t) //t表示扩展结点在解空间树中所处的层次
{if(tn) //n标识问题的规模output(x); //x是存放当前解的一维数组else{for(int it;in;i){swap(x[t],x[i]); //实现两个位置的交换if(constraint(t)bound(t)) //约束函数与限定函数backtrack(t1) //递归swap(x[t],x[i]); //恢复原状}}}解空间为排列树的常见问题 1n皇后问题 2旅行商问题 3园排列问题 4电路板排列问题。 满m叉树On*m^n
地图着色问题
每个元素有M种选择 二分搜索法最好O1 最坏Ologn 二分搜索法Binary Search是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始如果中间元素正好是要查找的元素则搜索过程结束如果某一特定元素大于或者小于中间元素则在数组大于或小于中间元素的那一半中查找而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空则代表找不到。 最好时间复杂度 在二分搜索法中如果我们要查找的元素正好是数组的中间元素那么我们只需要一次比较就能找到它。因此最好的情况下二分搜索的时间复杂度是 O(1)。但是严格来说我们通常说二分搜索的最好时间复杂度是 O(log n)因为这只是平均情况或最好情况的一种特例而平均情况或最好情况通常需要 log n 次比较当 n 是数组的长度时。 最坏时间复杂度 在二分搜索法中最坏的情况是我们要查找的元素不在数组中或者它在数组的最左边或最右边。在这种情况下我们需要不断地缩小搜索范围直到搜索范围为空。每次比较我们都将搜索范围减半因此在最坏的情况下我们需要 log n 次比较这里 log 是以 2 为底的对数。所以二分搜索的最坏时间复杂度是 O(log n)。 归并排序
#include iostream
using namespace std;void Merge(int A[], int low, int mid, int high)
{int* B new int[high - low 1];int i low, j mid 1, k 0;while (i mid j high){if (A[i] A[j])B[k] A[i];elseB[k] A[j];}while (i mid) B[k] A[i];while (j high) B[k] A[j];// 修正复制B到A时确保k从0开始 for (int p 0; p k; p)A[low p] B[p]; // 使用low p来确保复制到正确的位置 delete[] B; // 释放动态分配的内存
}void MergeSort(int A[], int low, int high)
{if (low high){int mid (low high) / 2;// 修正递归调用应该包括mid MergeSort(A, low, mid);MergeSort(A, mid 1, high);Merge(A, low, mid, high);}
}int main()
{int a[] { 1, 2, 54, 25, 76, 23 };int n sizeof(a) / sizeof(a[0]); // 计算数组长度 MergeSort(a, 0, n - 1); // 修正传入正确的high值 for (int i 0; i n; i) // 修正打印所有元素 cout a[i] ; // 添加空格分隔符 cout endl; // 打印换行符 return 0;
} 这三行代码是归并排序Merge Sort算法中的关键步骤。归并排序是一种分治Divide and Conquer策略的排序算法。 MergeSort(A, low, mid); 这行代码是递归地调用归并排序函数本身用于对数组的左半部分进行排序。这 2. MergeSort(A, mid 1, high); 这行代码与第一行类似但它是用于对数组的右半部分进行排序。 3. Merge(A, low, mid, high); 当左半部分和右半部分都已经被排序后这行代码用于将这两个已排序的子数组合并成一个已排序的完整数组。 快速排序
void QuickSort(int array[], int low, int high) {int i low; int j high;if(i j) {return;}int temp array[low];while(i ! j) {while(array[j] temp i j) {j--;}while(array[i] temp i j) {i;}if(i j) {swap(array[i], array[j]);}}//将基准temp放于自己的位置第i个位置swap(array[low], array[i]);QuickSort(array, low, i - 1);QuickSort(array, i 1, high);
}
