分析这段递归函数的时间复杂度void find(int i){ for(int j=1;j<=n;j++){ if(g[i][j]==1){ g[j][i]=g[i][j]=0; //擦除i-j的连线 find(j); } } c[++ci]=i; }
时间: 2024-05-22 14:16:47 浏览: 1
这段递归函数实际上是对一个图进行深度优先遍历,并将遍历的结果存储在数组c中。具体来说,对于当前节点i,依次遍历与其相邻的节点j,并将i和j之间的连线擦除,然后递归遍历j节点。当遍历完所有与i相邻的节点后,将i存储到数组c中。
时间复杂度分析:
遍历整个图需要遍历每个节点,而对于每个节点,需要遍历其相邻的节点,因此总的时间复杂度为O(n^2)。但是,在遍历过程中,每条边只会被遍历一次,并且每个节点也只会被遍历一次,因此实际的时间复杂度应该是O(m+n),其中m为边数。
相关问题
请详细解释下列代码:#include<iostream> #include<fstream> using namespace std; int MIN(int n, int m){ if (n > m) return m; else return n; } int MAXMUM(int i, int j){ if (i > j) return i; else return j; } int MAX(int *D, int i, int j){ int max, mid, max1, max2; if (i == j) max = D[i]; else if (i == j - 1) if (D[i] < D[j]) max = D[j]; else max = D[i]; else { mid = (i + j) / 2; max1 = MAX(D, i, mid); max2 = MAX(D, mid + 1, j); max = MAXMUM(max1, max2); } return max; } void SORT(int P[], int D[],int foo[], int start, int end)//按效益大到小排序 { for (int i = start + 1; i <= end; i++) { int item = P[i]; int item_d = D[i]; int item_f=foo[i]; int j = i - 1; while (j >= start && item > P[j]) { P[j + 1] = P[j]; D[j + 1] = D[j]; foo[j+1]=foo[j]; j--; } P[j + 1] = item; D[j + 1] = item_d; foo[j+1]=item_f; } } int FIND(int *parent, int i){ int j, k, t; j = i; while (parent[j] > 0) j = parent[j];//根 k = i; while (k != j) { t = parent[k]; parent[k] = j; k = t; } return j; } void UNION(int *parent, int i, int j){ int x; x = parent[i] + parent[j]; if (parent[i] > parent[j]) //i的结点少 { parent[i] = j; parent[j] = x; } else { parent[j] = i; parent[i] = x; } } int FJS(int *D, int n, int b, int *J, int *Q){ int i, j, l, k; int *F = new int[n]; int *P = new int[n]; for (i = 0; i <= b; i++) { F[i] = i; P[i] = -1; } k = 0;//初始化J for (i = 1; i <= n; i++){ j = FIND(P, MIN(n, D[i])); if (F[j]!= 0){ k = k + 1; J[k] = i; Q[F[j]] = i; l = FIND(P, F[j] - 1); UNION(P, l, j); F[j] = F[l]; } } return k;//返回最优解的个数 } int main(){ int n, p, d, i, b, k; cin >> n;//作业数 int P[n];//效益 int D[n];//期限 int J[n];//解集 int Q[n];//顺序 int foo[n];//脚标 for (int i = 1; i <= n; i++){ cin >>d>> p; P[i] = p; D[i] = d; foo[i]=i; } SORT(P, D,foo, 1, n); b= MIN(n, MAX(D, 1, n)); for (i = 1; i <= b; i++) Q[i] = -1; k = FJS(D, n, b, J, Q); int sum = 0; for (int i = 1; i <= b; i++){ if (Q[i] != -1) { sum += P[Q[i]]; } } cout << sum << endl; for (int i = 1; i < b; i++) if (Q[i] != -1){ cout <<foo[Q[i]]<< " "; } cout<<foo[Q[b]]; return 0; }
这段代码实现了一个贪心算法,用于解决作业调度问题。具体来说,有n个作业,每个作业有一个效益P和一个期限D,要求将这些作业调度到一个时间轴上,使得效益最大化,同时满足每个作业的完成时间不超过其期限。该算法的主要思路是按照效益从大到小排序,然后依次将作业加入时间轴中,如果在加入某个作业时发现其期限已经过了,则将其舍弃。
该算法中的主要函数包括:
1. MIN函数:返回两个整数中的较小值。
2. MAXMUM函数:返回两个整数中的较大值。
3. MAX函数:递归地求解一个数组中的最大值。
4. SORT函数:按照效益从大到小对作业进行排序。
5. FIND函数:查找某个作业的根节点。
6. UNION函数:将两个作业合并到同一个集合。
7. FJS函数:实现贪心算法的主要部分,返回最优解的个数。
8. main函数:读入作业信息,按照效益排序,调用FJS函数求解最优解,并输出结果。
该算法的时间复杂度为O(nlogn),其中n为作业数量,主要开销在排序和查找根节点上。
用c++的方式采用递归回溯法设计一个算法求 1~n 的 n 个整数中取出 m 个元素的排 列,要求每个元素最多只能取一次。(问题设定:n=3,m=2)并写出实验分析
好的,我了解了你的问题。下面是 C++ 的递归回溯法实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
void backtrack(vector<int>& res, vector<int>& nums, int m) {
if (res.size() == m) {
for (int i = 0; i < m; i++) {
cout << res[i] << " ";
}
cout << endl;
return;
}
for (int i = 0; i < nums.size(); i++) {
if (find(res.begin(), res.end(), nums[i]) != res.end()) {
continue;
}
res.push_back(nums[i]);
backtrack(res, nums, m);
res.pop_back();
}
}
int main() {
int n = 3, m = 2;
vector<int> res, nums(n);
for (int i = 0; i < n; i++) {
nums[i] = i + 1;
}
backtrack(res, nums, m);
return 0;
}
```
该算法的基本思想是利用递归回溯法生成所有可能的排列,具体实现如下:
- 定义一个 res 数组,用于存储当前已经选择的数字。
- 如果 res 数组的长度为 m,说明已经选择了 m 个数字,输出当前排列并返回。
- 枚举 nums 数组中的每个数字,如果该数字已经在 res 数组中出现过了,则跳过。
- 将当前数字添加到 res 数组中。
- 递归调用 backtrack 函数,从剩余的数字中继续选择数字。
- 在递归返回后,将 res 数组中的最后一个数字弹出,开始枚举下一个数字。
对于 n=3,m=2 的情况,算法的输出如下:
```
1 2
1 3
2 1
2 3
3 1
3 2
```
实验分析:
该算法的时间复杂度为 O(n!),其中 n 表示待排列的元素个数。该算法的空间复杂度为 O(n),即存储当前排列的数组的长度。当 n 的值较大时,该算法的时间复杂度会非常高,因此不适用于大规模的排列问题。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)