106 lines
2.9 KiB
Markdown
106 lines
2.9 KiB
Markdown
# 经典算法实验报告
|
||
|
||
## 一、实验内容
|
||
|
||
本次完成 4 个实验：
|
||
|
||
| 模块 | 实验 |
|
||
|---|---|
|
||
| 分治 | 1-B-1 基于分治找最大值 |
|
||
| 动态规划与贪心 | 2-B-1 装配线调度二分分治与 DP |
|
||
| 动态规划与贪心 | 2-B-2 矩阵链乘贪心与 DP 对比 |
|
||
| 常规搜索 | 3-B-1 皇后问题回溯算法 |
|
||
|
||
## 二、实验过程与结果
|
||
|
||
### 1. 分治找最大值
|
||
|
||
算法思路：将数组二分，分别求左右子数组最大值，再取二者较大值。
|
||
|
||
复杂度：
|
||
|
||
- 时间复杂度：`T(n)=2T(n/2)+O(1)=O(n)`
|
||
- 空间复杂度：递归栈 `O(log n)`
|
||
|
||
测试：随机生成数组，与顺序扫描结果对比，测试通过。
|
||
|
||
基准结果：
|
||
|
||
| 数据规模 | 时间 |
|
||
|---:|---:|
|
||
| 1000 | 2214 ns/op |
|
||
| 100000 | 215274 ns/op |
|
||
|
||
结论：运行时间随输入规模近似线性增长，符合 `O(n)` 分析。
|
||
|
||
### 2. 装配线调度
|
||
|
||
实现了两种算法：
|
||
|
||
- 动态规划：从左到右计算到达两条生产线每个工位的最小时间。
|
||
- 二分分治：将工位从中间分成左右两段，递归计算子问题，再合并两段之间的换线代价。
|
||
|
||
复杂度：
|
||
|
||
| 算法 | 时间复杂度 | 空间复杂度 |
|
||
|---|---:|---:|
|
||
| DP | `O(n)` | `O(n)` |
|
||
| 二分分治 | `O(n)` | `O(log n)` |
|
||
|
||
测试：对长度 `1..128` 的随机数据，每个长度测试 200 组，二者结果完全一致。
|
||
|
||
基准结果：
|
||
|
||
| 算法 | n=1000 | n=100000 |
|
||
|---|---:|---:|
|
||
| DP | 3531 ns/op | 323679 ns/op |
|
||
| 二分分治 | 5959 ns/op | 632573 ns/op |
|
||
|
||
结论：两种算法同为线性时间；本实现中 DP 更快，但需要额外数组，分治版无堆分配。
|
||
|
||
### 3. 矩阵链乘
|
||
|
||
实现了：
|
||
|
||
- DP 最优算法：枚举断点，求最少标量乘法次数。
|
||
- 贪心算法：每次优先消去最大中间维度。
|
||
|
||
复杂度：
|
||
|
||
| 算法 | 时间复杂度 | 空间复杂度 |
|
||
|---|---:|---:|
|
||
| DP | `O(n^3)` | `O(n^2)` |
|
||
| 贪心 | `O(n^2)` | `O(n)` |
|
||
|
||
测试结果：
|
||
|
||
- 经典样例 `[30,35,15,5,10,20,25]`，DP 结果为 `15125`。
|
||
- 随机测试中未出现贪心优于 DP 的情况。
|
||
- 找到反例：`[5,6,5,4]`，贪心结果 `250`，DP 最优结果 `240`。
|
||
|
||
结论：贪心速度较快，但不能保证最优；DP 能保证最优解。
|
||
|
||
### 4. 皇后问题回溯
|
||
|
||
算法思路：逐行放置皇后，用列数组、主对角线数组、副对角线数组判断当前位置是否冲突；若合法则继续递归，否则回溯。
|
||
|
||
复杂度：
|
||
|
||
- 时间复杂度：最坏约 `O(n!)`
|
||
- 空间复杂度：`O(n)`
|
||
|
||
测试输入 `n=8`，输出前 3 个解，并统计总解数：
|
||
|
||
```text
|
||
1 5 8 6 3 7 2 4
|
||
1 6 8 3 7 4 2 5
|
||
1 7 4 6 8 2 5 3
|
||
92
|
||
```
|
||
|
||
结论：8 皇后共有 92 个可行解，程序输出正确。
|
||
|
||
## 三、实验总结
|
||
|
||
本次实验验证了分治、动态规划、贪心和回溯算法的基本特点：分治适合递归拆分问题；动态规划能保证全局最优；贪心效率高但可能非最优；回溯适合枚举约束解空间，但规模增大后搜索代价较高。
|