经典算法实验报告

一、实验内容

本次完成 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 个解，并统计总解数：

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 个可行解，程序输出正确。

三、实验总结

本次实验验证了分治、动态规划、贪心和回溯算法的基本特点：分治适合递归拆分问题；动态规划能保证全局最优；贪心效率高但可能非最优；回溯适合枚举约束解空间，但规模增大后搜索代价较高。