Czj's Blog

算法设计与分析-第一章

发表于 更新于 分类于
本文字数： 15k 阅读时长 ≈ 14 分钟

推销员问题

骑士周游列国

码头扩建

算法时间复杂度分析

推销员问题（TSP）

题目大意

推销员问题（Traveling Salesman Problem，TSP）是一个经典的组合优化问题。在该问题中，一个推销员需要访问一系列城市，每个城市只能访问一次，最后必须回到起始城市，目标是找到一条总路径长度最短的路线。从图论角度看，可将城市视为图的节点，城市之间的路径视为图的边，边的权重表示城市间的距离，问题等价于在完全图中寻找最小权重的哈密尔顿回路。

解法描述

朴素穷举+剪枝优化

  1. 算法思想

    通过枚举所有可能的城市访问顺序，计算每种顺序下的路径总长度，从而找出最短路径。利用贪心法进行剪枝，在枚举过程中，如果当前路径长度已经大于已知的最小路径长度，停止对该路径后续情况的枚举。

  2. 实现方式

    在 C++中，借助 next_permutation 函数来枚举所有城市排列。对每个排列，依次计算相邻城市间的距离并累加，得到该排列对应的路径长度。在计算过程中，一旦路径长度超过当前记录的最小路径长度，直接放弃该排列的后续计算。

  3. 复杂度分析

    • 时间复杂度：朴素穷举的时间复杂度为\(O(n!)\)，因为需要枚举\(n\)个城市的所有排列。虽然剪枝优化在一定程度上减少了不必要的计算，但在最坏情况下，时间复杂度仍然是\(O(n!)\)。当城市数量\(n\)较大时，计算量会急剧增加，导致算法效率极低。
    • 空间复杂度：主要取决于存储每个排列的空间，由于只需要存储一个城市排列序列，所以空间复杂度为\(O(n)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
// 朴素解，用next_permutation函数枚举所有城市排列，在所有可能的路径长度中取最小的。最坏时间复杂度为O(n!)
vector<vector<int>> g;
vector<int> cities;
const int INF = 0x3f3f3f3f; // 视为无穷大
int n, final_ans = INF, x; // 城市数量
int compute(const vector<int>& path) {
	int ans = 0;
	for (int i = 0; i < path.size() - 1; i++) {
		ans += g[path[i]][path[i + 1]]; // 从第i个城市到第i+1个城市
		if (ans > final_ans) {
			return final_ans;
		}
	}
	return ans;
}
int solve_TSP() {
	vector<int> cities(n);// 城市遍历序列
	for (int i = 0; i < n; i++) {
		cities[i] = i;//初始化
	}
	do {
		int tmp = compute(cities);
		final_ans = min(final_ans, tmp);
	} while (next_permutation(cities.begin() + 1, cities.end())); // 用next_permut交换各个城市的相对位置
	return final_ans;
}
int main() {
	cin >> n;
	g.resize(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> x;
			if (x == -1) x = INF;
			g[i][j] = x;
		}
	}
	cout << solve_TSP() << endl;
	return 0;
}

动态规划法（Bellman - Held - Karp 算法）

  1. 算法思想

    将原问题划分为多个子问题，通过求解子问题的最优解，逐步构建出原问题的最优解。把所有可能的路径用二进制序列表示，其中 1 表示对应城市已走过，0 表示未走过。利用状态转移方程，根据已走过城市的状态和当前所在城市，计算出走到下一个未走过城市的最小消耗。

  2. 实现方式

    定义两个二维数组 dp 和 path，dp[i][j] 表示当前走过的城市状态为 i （二进制表示）且当前位于城市 j 时的最小消耗；path[i][j] 记录走到城市 j （状态为 i 时）的前一个城市。通过三层循环，外层循环遍历所有可能的城市状态（从 \(1\) 到 \(2^n - 1\)），中层循环在当前状态下遍历所有城市找到已走过的城市 u，内层循环遍历所有城市找到未走过的城市 v，更新 dp 数组和 path 数组。最后，通过遍历所有城市，找到从所有城市回到起始城市的最小路径长度，并根据 path 数组回溯出具体路径。

  3. 复杂度分析

    • 时间复杂度：算法中有三层循环，外层循环遍历\(2^n\)种城市状态，中层和内层循环分别遍历\(n\)个城市，所以时间复杂度为\(O(n^2\times2^n)\)。尽管它仍然是指数级复杂度，但相比朴素穷举的\(O(n!)\)，在实际计算中，由于利用了子问题的重叠性质，减少了重复计算，通常能在更短时间内找到最优解。
    • 空间复杂度：主要由存储子问题最优解的二维数组 dp 和 path 决定，它们的大小都是\((2^n)\times n\)，所以空间复杂度为\(O(n\times2^n)\)。当\(n\)较大时，可能会面临内存不足的问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

#include <bits/stdc++.h>
using namespace std;
/*
  使用Bellman-Held-Karp算法，时间复杂度O((2^n)*(n^2))
  开两个vector<vector<int>, int>数组，大小为(2^n)*n，以空间换时间
  本算法将所有的可能路径视为二进制序列，1为已经走过，0为未走过。
  不难发现，n个城市一共有2^n种序列，因此遍历他们总共需要2^n次
  同时在每次选取了一个序列后，还需要用双重循环来：1.在已经走过的路径中选择一个出发点 2.选择接下来要走的点（不能已经在集合中），增加将边权加入dist
 */
//可以处理n=23的问题，并且耗时较少。但是n更大会导致无法分配足够内存而报错

const int INF = 0x3f3f3f3f;

vector<vector<int>> dp;
vector<vector<int>> path;
vector<vector<int>> g;

int final_ans, n, start_idx;
//void init() {
//	//用assign填充
//	g.assign(n, vector<int>(n, INF));
//	for (int i = 0; i < n; i++) {
//		for (int j = i + 1; j < n; j++) g[i][j] = g[j][i] = rand() % 100 + 1;
//	}
//	dp.assign(1 << n, vector<int>(n, INF));
//	path.assign(1 << n, vector<int>(n, -1));
//	start_idx = 0;
//	dp[1 << start_idx][start_idx] = 0; //从0号城市回到0号的距离为0
//}
void init() {

}
void Bellman_Held_Karp() {
	/*
	  dp和path的第一维用于记录当前走过的城市，第二维用于记录本次走到的终点
	  dp的值表示走法的最小消耗,path的值表示走终点的前一个点是谁
	 */
	for (int i = 1; i < (1 << n); i++) { //遍历2^n-1次，i是十进制表示的二进制序列
		for (int u = 0; u < n; u++) { //遍历所有点，找到已经在集合中的
			if (i & (1 << u)) { //1<<u表示二进制序列中第u为是1，用&来判断第u位是否都是1，是则表明点u已经在当前的路径中了
				//选取城市u，试图以其为起点走到城市v
				for (int v = 0; v < n; v++) {
					if (!(i & (1 << v))) { //如果v还没走过，那就不会形成环路，可以走
						if (dp[i | (1 << v)][v] > dp[i][u] + g[u][v]) {
							dp[i | (1 << v)][v]  = (dp[i | (1 << v)][v], dp[i][u] + g[u][v]); //检测从u走到v是否会使得路径边长，更新路径集合和其对应的值
							path[i | (1 << v)][v] = u;
						}

					}
				}
			}
		}
	}
	//添加最后构成回环的路径
	int final_que = (1 << n) - 1; //全为1的二进制序列
	final_ans = INF;
	int last_city = -1;
	for (int t = 0; t < n; t++) { //再次遍历所有点
		int tmp = dp[final_que][t];//tmp表示走过了所有点后，回到点t
		int last_w = g[t][start_idx];//最后一条边的权重
		if (tmp + last_w < final_ans) {
			final_ans = tmp + last_w;
			last_city = t;
		}
	}
	//读出path中存的点作为路径
	vector<int> path_ans;
	//因为是环路，所以可以从后往前记录
	int current_city = last_city;
	int current_set = final_que;
	while (current_city != -1) { //-1是path数组的初始值
		path_ans.push_back(current_city);
		current_set ^= (1 << current_city); //将当前城市从集合中删除
		current_city = path[current_set | (1 << current_city)][current_city];
		//上一个城市是以这个城市为终点的边的起点，要暂时补回删掉的城市

	}
	cout << "序列表示哈密顿回路" << endl;
	cout << start_idx << " ";
	for (auto x : path_ans) {
		cout << x << " ";
	}

	puts("");

}
void print_g() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) cout << g[i][j] << " ";
		puts("");
	}

}
int main() {
	cin >> n;
	init();
//	print_g();
//	clock_t start_t = clock();
	Bellman_Held_Karp();
//	clock_t end_t = clock();
//	cout << "最短路径权值为" << final_ans << endl;
	cout << final_ans << endl;
//	double elapsed_time = (double)(end_t - start_t) / CLOCKS_PER_SEC;
//	cout << "耗时为" << (elapsed_time) << "s";
	return 0;
}

骑士周游列国

题目大意

在国际象棋 8×8 的棋盘上，给定骑士的初始位置(\(m\),\(n\))（其中 \(0\leq m,n\leq 8\) ），要求找出一条路径，使骑士不重不漏地经过棋盘上的每一个格子。路径需用 8×8 的矩阵输出，矩阵中每个元素的值表示骑士到达该位置时行走的步数，起始位置步数为 1。

解法描述

深度优先遍历 DFS

  1. 算法思想

    深度优先搜索是一种“试错”的搜索策略。从起始位置开始，按照骑士的移动规则，尝试所有可能的走法。若当前走法能继续推进（新位置未被访问过），则标记该位置并递归继续探索；若当前位置的所有走法都无法推进（新位置已被访问或越界），则回溯到上一个位置，尝试其他未探索的走法，直至遍历完整个棋盘或确定不存在可行路径。

  2. 实现方式

    使用一个二维数组 g[N][N] 表示棋盘，其中 N = 8。数组元素值为 0 表示该位置未被访问，非 0 值表示骑士到达该位置的步数。定义方向数组 dx[8] 和 dy[8] 来表示骑士的 8 种移动方向。在 dfs 函数中，每次递归时检查当前位置的 8 个可能移动方向，若新位置合法且未被访问，则标记新位置并递归调用 dfs 继续探索，若递归返回 true 说明找到了可行路径，直接返回；若所有方向都尝试完仍未找到可行路径，则回溯（将新位置标记回 0）并返回 false。在主函数中，读入起始位置，初始化起始位置的步数为 1，调用 dfs 函数进行搜索，若找到路径则输出棋盘矩阵，否则输出提示信息。

  3. 复杂度分析

    • 时间复杂度：在最坏情况下，每个位置都要尝试 8 种走法，对于 8×8 的棋盘，共有 64 个位置。随着搜索的深入，分支数量呈指数增长，所以时间复杂度约为 \(O(8^{64})\)，这是一个非常高的时间复杂度，意味着在大规模问题下，算法效率极低。
    • 空间复杂度：空间复杂度主要取决于递归调用栈的深度。因为在最坏情况下需要遍历整个棋盘，而每次递归调用都会在栈中占用一定空间，递归深度最大为 64，所以空间复杂度为 \(O(N^{2})\)，即 \(O(64)\) 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
  本题需要在8*8棋盘中，从一个点出发找到遍历所有点的一条路径
  关键点：每个点都有8种可能的走法，但是最终只需要找到一条可以遍历所有点的路径
  因此采用dfs递归搜索，并增加返回值以表示当前所走的方向是否正确，确保在找到一条正确路径后就结束
 */
#include <bits/stdc++.h>
using namespace std;
int n, m, step;
const int N = 8;
int g[N][N];
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
bool check(int x, int y) {
	return x >= 0 && x < N && y >= 0 && y < N;
}
bool dfs(int x, int y, int step) {
	if (step > 64) {
		return true;  // 找到路径后返回 true
	}
	for (int i = 0; i < 8; i++) {
		int tx = x + dx[i], ty = y + dy[i];
		if (check(tx, ty) && g[tx][ty] == 0) {
			g[tx][ty] = step;
			if (dfs(tx, ty, step + 1)) return true; //如果是合适的路径，那就不需要回溯
			else g[tx][ty] = 0;
		}
	}
	return false;
}
int main() {
	cin >> n >> m;
	g[n][m] = 1;
	if (dfs(n, m, 2)) {
		// 如果找到路径，输出路径
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cout << g[i][j] << ' ';
			}
			puts("");
		}
	} else {
		cout << "No solution found." << endl;
	}

	return 0;
}

启发式搜索 Warnsdorff 规则

  1. 算法思想

    Warnsdorff 规则是一种启发式策略，其核心是在当前位置选择一阶落点时，优先考察各个一阶落点的可行二阶落点个数，选择可行二阶落点个数最少的一阶落点作为下一步移动方向。这样做的目的是优先选择那些周围“出路”较少的位置，使搜索更有针对性，减少不必要的回溯，提高搜索效率。

  2. 实现方式

    在原 DFS 代码基础上进行修改。定义一个函数 get_weight 来计算某个位置的可行二阶落点个数。在每次选择下一步移动位置时，将所有可行的一阶落点及其权重（可行二阶落点个数）存入一个向量 v 中，然后对向量 v 按权重从小到大排序。优先尝试权重小的落点进行递归搜索，若找到可行路径则返回，否则回溯继续尝试其他落点。

  3. 复杂度分析

    • 时间复杂度 在最坏情况下，检查每个位置的邻居时，需要考虑所有可能的移动位置，这里邻居个数 \(N = 8\)，时间复杂度为 \(O(N^{2})\)，即 \(O(8^{2}) = O(64)\)。但实际上，由于 Warnsdorff 规则的引导，搜索过程会优先选择更有可能成功的路径，大幅减少了搜索范围，基本可在线性时间内检测完棋盘上的所有点，相比朴素 DFS 的指数级复杂度有显著优化。
    • 空间复杂度 空间复杂度与 DFS 类似，主要取决于递归深度或栈的大小。在最坏情况下，同样为 \(O(N^{2})\) （\(N\) 是棋盘边长），即 \(O(64)\)。不过，由于 Warnsdorff 规则的引导，搜索路径从八叉树退化为二叉树，使得递归深度降低。虽然这对空间复杂度的理论影响不大，但在实际运行中，对于只需求一个可行解的情况，实际空间利用效率更高，减少了不必要的空间占用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*
  Warnsdorff规则：
  在当前位置(x,y)选择一阶落点时，先考察各个一阶落点的可行二阶落点个数，选择其中可行二阶落点个数最少一阶落点（以下暂记这个一阶落点为可行方向）
  有效性分析：
  本规则要求每次选择可行方向，不难发现，在周游初期，这个方向一定是存在的。而在后期，如果能完成一次巡游，那么可行方向也必须存在。
  因此可行方向一定可以构成一个正确回路（当然正确回路不一定是由可行方向组成的），由于本题只需要一个解，所以该规则有效

  综上，在得知Warnsdorff规则后，我们就可以对dfs进行剪枝了，以每个一阶落点的二级落点个数作为权值，从而可以将原来的满8分叉树化简为二叉或三叉树，从而更快地找到一个答案
 */
#include <bits/stdc++.h>
#define  x first
#define  y second
using namespace std;
typedef pair<int, int> PII;
typedef pair<int, PII> PIPII;
const int N  = 8;
int g[N][N], x, y;
PII direc[N] = { {1, -2}, {2, 1}, {2, -1}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}, {1, 2}};

bool ok(int x, int y) {
	return x >= 0 && x < N && y >= 0 && y < N && g[x][y] == 0;
}
void print_g() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << g[i][j] << " \n"[j == N - 1];
		}
	}
}
int get_weight(int x, int y) {
	int tx, ty, res = 0;
	for (int i = 0; i < N; i++) {
		tx = x + direc[i].x, ty = y + direc[i].y;
		if (ok(tx, ty)) res++;
	}
	return res;
}
bool dfs(int x, int y, int step) { //设置为bool类型以期在找到答案的第一时间结束递归
	if (step == 65) return true;
	int tx, ty;
	vector<PIPII> v;//存放本次检测的所有一阶落点和他们的权重
	for (int i = 0; i < N; i++) {
		tx = x + direc[i].x, ty = y + direc[i].y;
		if (ok(tx, ty))v.push_back({get_weight(tx, ty), {tx, ty}});
	}
	sort(v.begin(), v.end());
	for (auto t : v) {
		g[t.y.x][t.y.y] = step;
		if (dfs(t.y.x, t.y.y, step + 1)) return true;
		g[t.y.x][t.y.y] = 0;
	}
	return false;
}
int main() {
	cin >> x >> y;
	g[x][y] = 1;
	dfs(x, y, 2);
	print_g();
	return 0;
}

一种可能的周游路径如下： img

码头扩建问题

题目大意

某市有一码头，每次仅允许一艘船停泊装卸货。根据历史资料，码头平均每月停船 24 艘，每艘船的停泊时间为 24±20 小时，相邻两艘船的到达时间间隔为 30±15 小时。若一艘船因有其他船在港而等候 1 小时，其消耗成本为 1000 元。扩建码头大约需要 1350 万元。要求通过程序随机产生到达时间和停泊时间，模拟未来五年内船的停泊情况，多次模拟预测停泊情况，以判断未来五年内停泊船只因等候的成本消耗总和是否超过扩建码头花费，从而帮助市长做出是否扩建码头的决策。

解法描述

离散事件模拟算法

  1. 算法思想

    利用离散事件模拟的方法，将未来五年的时间按月划分，通过循环模拟每个月内船只的到达和停泊过程。在模拟过程中，借助随机数生成符合条件的船只到达时间间隔和停泊时间，根据船只到达时码头的状态（是否有船正在停泊）来计算等待时间和成本，最后累加所有模拟次数的成本并求平均，与扩建码头的成本阈值进行比较，得出是否扩建的结论。

  2. 实现方式

    在 C++中，使用 <random> 库生成随机数。random_device rd 用于生成随机数种子，mt19937 gen(rd()) 创建一个基于种子的随机数生成器。通过两层嵌套循环进行模拟，外层循环控制模拟的总次数（如 1000 次），内层循环模拟每个月（共 60 个月）的情况。对于每个月，假设第一艘船在最开始到达，生成其停泊时间。后续船只根据上一艘船的到达和停泊时间计算自身到达时间，若到达时上一艘船还在停靠，则计算等待成本，更新停泊时间；若无需等待，则直接更新停泊时间。每次模拟结束后累加总成本，最后根据总成本与扩建成本阈值的比较结果输出决策信息。

  3. 复杂度分析

    • 时间复杂度：外层循环执行次数为模拟总次数，设为 test，时间复杂度为 \(O(test)\)。内层循环执行 60 次，内层循环中的计算操作，如随机数生成、条件判断和成本计算等，都是常数时间操作，时间复杂度为 \(O(1)\)。所以总体时间复杂度为 \(O(test×1)\)，即 \(O(test)\) 。当模拟次数增加时，运行时间会线性增长。
    • 空间复杂度：程序中主要使用了几个整型变量（如 spend、dock_time、arrival_time 等）和一个长整型变量（cost）来存储数据，这些变量占用的存储空间是常数级别的。随机数生成器的存储空间与生成器的状态大小相关，但在本实验中，其状态大小也是常数级别的，不会对空间复杂度产生显著影响。因此，总体空间复杂度为 \(O(1)\) ，即无论模拟次数和数据规模如何变化，程序占用的空间基本保持不变。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
/*
  为了简化情况，本模拟将五年按月划分开，即以一个月为基础编写代码，并循环5*12次
 */
const long long  Max = 1.35e7;
int spend, pre = 1000;
int dock_time, arrival_time;
long long cost, tmp_cost;
int main() {
	//生成随机数
	random_device rd;//声名一个随机数种子对象。命名为rd
	mt19937 gen(rd());//创建了一个 mt19937 类的对象，它使用前面声明的 rd 对象生成的种子进行构造。这个对象被命名为 gen。
	//uniform_int_distribution<>，均匀分布的随机数生成器
	//下述的arrival_interval和docking_time是一个类，接受gen作为参数
	uniform_int_distribution<> arrival_interval(15, 45);//到达时间
	uniform_int_distribution<> docking_time(4, 44);//停泊时间
//进行一千次模拟
	for (int t = 1; t <= 1000; t++) {
		tmp_cost = 0;
		for (int month = 1; month <= 60; month++) {
			//不考虑从月末停留到月初的情况
			//不妨假设第一艘船是在最开始到达的
			dock_time = arrival_time = 0;
			for (int ship = 1; ship <= 24; ship++) {
				if (ship == 1) {
					dock_time = docking_time(gen);//开始卸货
				} else {
					//本船到达
					arrival_time += arrival_interval(gen);//增加表示间隔时间
					if (arrival_time < dock_time) {
						//到达时上一艘船还在停靠

						tmp_cost += (dock_time - arrival_time) * pre;
						dock_time += docking_time(gen); //本船还不能进港操作，必须等上一只船结束
					} else dock_time = arrival_time + docking_time(gen); //无需等待，那就是入港时间加自身卸货
				}
//				dock_time = docking_time(gen);
//				arrival_time = arrival_interval(gen);
//				if (dock_time > arrival_time) tmp_cost += 1000 * (dock_time - arrival_time);
			}
		}
		cost += tmp_cost / 1000;
	}

	if (cost > Max) cout << "超支了" << cost - Max << "元" << "应该扩建" << endl;
	else printf("距离超支还有%lld元，不用扩建", (Max - cost));
	return 0;
}

算法时间复杂度的实验测试

题目大意

运用编程工具对堆排序或快速排序算法进行时间复杂度测试，通过在不同输入规模下运行算法并记录运行时间，从而学会通过实验分析算法的时间复杂度。

解法描述

堆排序算法

  1. 算法思想

    基于二叉堆数据结构，以构建大根堆为例实现从小到大排序。首先将输入数组进行堆化操作，使每个节点都满足大根堆性质，即父节点的值大于等于子节点的值。然后不断将堆顶元素（最大值）与数组末尾元素交换，将最大值放到数组末尾，接着对交换后的堆进行调整，维持堆的性质，重复该过程直到整个数组有序。

  2. 实现方式

    在 C++代码中，定义数组 heap[N] 存储待排序数据，N 为数组最大容量。down 函数用于调整堆，在函数中，通过比较当前节点与其左右子节点的值，将最大值交换到当前节点位置，并递归向下调整。在 main 函数中，利用 <random> 库生成随机数填充数组。排序前使用 clock() 函数记录起始时间，排序过程先对数组进行堆化（从 n/2 到 0 调用 down 函数），然后通过不断交换堆顶和末尾元素并调整堆（共 n 次）实现排序。排序结束后再次使用 clock() 函数记录结束时间，计算并输出排序耗时。

  3. 复杂度分析

    • 时间复杂度：堆排序的时间复杂度为 \(O(n log n)\)。堆构建阶段，从 n/2 到 0 调用 down 函数，每次调整操作的时间复杂度为 \(O(log n)\)，总共进行约 \(n/2\) 次，时间复杂度为 \(O(n log n)\) ；排序阶段，进行 n 次交换和调整堆操作，每次调整堆的时间复杂度也是 \(O(log n)\)，整体排序阶段时间复杂度同样为 \(O(n log n)\)。
    • 空间复杂度：堆排序仅使用了常数级别的额外空间，如在调整堆过程中临时变量的存储，因此空间复杂度为 \(O(1)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
const int N = 1e8;
int heap[N];//大根堆实现从小到大排列
int n;
void down(int idx) {
	int tmp = idx;
	//大根堆的根应该是最大的
	//在idx，2*idx+1，2*idx三者中找到值最大的那一个
	if (2 * idx <= n && heap[tmp] < heap[idx * 2]) tmp = idx * 2;
	if (2 * idx + 1 <= n && heap[tmp] < heap[idx * 2 + 1]) tmp = idx * 2 + 1;
	if (tmp != idx) {
		swap(heap[idx], heap[tmp]);//让最大值来到根的位置
		down(tmp);//递归向下交换，使小的值向下，大的值向上
	}
	return;
}
int main() {
	//生成随机数构造器
	random_device rd;//声名一个随机数种子对象。命名为rd
	mt19937 gen(rd());//创建了一个 mt19937 类的对象，它使用前面声明的 rd 对象生成的种子进行构造。这个对象被命名为 gen。
	uniform_int_distribution<> random_num(0, 10000000);//均匀分布的随机数
	//填充随机数
	cin >> n;
	for (int i = 1; i <= n; i++) {
		//从一开始存避免找子节点时找到自己
		heap[i] = random_num(gen);
	}
	//排序开始
	clock_t start_t = clock();
	for (int i = n / 2; i >= 0; i--) {
		down(i);
	}
	int i = 1;
	while (i <= n) {
		swap(heap[1], heap[n]);//交换n次，将大值放在尾部，相当于从堆里剔除
		n--;
		down(1);
		i++;
	}
	clock_t end_t = clock();
	double elapsed_time = (double)(end_t - start_t) / CLOCKS_PER_SEC * 1000;
	cout << "耗时为" << (elapsed_time) << "ms";
	return 0;
}

快速排序算法

  1. 算法思想

    采用分治策略。选择一个基准元素，将数组分为两个子数组，使得左边子数组的元素都小于基准元素，右边子数组的元素都大于基准元素。然后递归地对左右子数组进行排序，最后合并各个有序子数组得到最终的有序数组。

  2. 实现方式

    代码中定义数组 q[N] 存储数据。quick_sort 函数实现快速排序逻辑，函数中先选取一个基准元素（这里取数组中间元素 q[(l + r) >> 1]），通过双指针 i和 j从数组两端向中间扫描，将小于基准的元素放到左边，大于基准的元素放到右边。当 i 和 j 相遇时，完成一次划分，接着递归对左右子数组进行排序。在 main 函数中，同样利用 <random> 库生成随机数填充数组，记录排序前后的时间，计算并输出排序耗时。

  3. 复杂度分析

    • 时间复杂度：快速排序平均时间复杂度为 \(O(n log n)\)。在平均情况下，每次划分都能将数组大致均匀分成两部分，递归深度为 \(log n\)，每层划分操作的时间复杂度为 \(O(n)\)，整体时间复杂度为 \(O(n log n)\)。但在最坏情况下，如每次选取的基准元素都是数组中的最大或最小值，划分会极度不均匀，时间复杂度会退化为 \(O(n^2)\) 。
    • 空间复杂度：快速排序的空间复杂度主要取决于递归调用的栈空间。平均情况下，递归深度为 \(log n\)，因此空间复杂度为 \(O(log n)\)；在最坏情况下，递归深度达到 \(n\)，空间复杂度为 \(O(n)\) 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
const int N = 1e8;
int q[N];//大根堆实现从小到大排列
int n;
void quick_sort(int q[], int l, int r) {
	if (l >= r) {
		return;//左右指针相遇
	}
	int x = q[(l + r) >> 1]; //随便取一个标定
	int i = l - 1, j = r + 1;//选不可能点
	while (i < j) {
		do i++;
		while (q[i] < x);
		do j--;
		while (q[j] > x);
		if (i < j) {
			swap(q[i], q[j]);
		}
	}
	//结束后[l,j]的数都比x要小，[j+1,r]的数都比x要大
	quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
int main() {
	//生成随机数构造器
	random_device rd;//声名一个随机数种子对象。命名为rd
	mt19937 gen(rd());//创建了一个 mt19937 类的对象，它使用前面声明的 rd 对象生成的种子进行构造。这个对象被命名为 gen。
	uniform_int_distribution<> random_num(0, 10000000);//均匀分布的随机数
	//填充随机数
	cin >> n;

	for (int i = 0; i < n; i++) {
		q[i] = random_num(gen);
	}
	clock_t start_t = clock();
	quick_sort(q, 0, n - 1);
	clock_t end_t = clock();
	double elapsed_time = (double)(end_t - start_t) / CLOCKS_PER_SEC * 1000;
	cout << "耗时为" << (elapsed_time) << "ms";
	return 0;
}