简介一份面向西南交通大学“算法分析与设计”课程的学习资料包将实验报告、预习报告与作业整合在29个文件中。22个docx用于存放各次实验的完整文档6个cpp为配套算法实现源码另含1本PDF版学生教程压缩包整体约41.72MB。内容围绕排序、查找、图算法等经典主题展开细致呈现实验目的、算法介绍、实现过程、复杂度分析与结果讨论作业部分则提供应用练习与优化思路。覆盖快速排序、二分查找、Dijkstra这类常用算法能够帮助学生理解算法效率评估方法。目前已有260人学习下载特别适合正在修读算法课程、需要参考实验写法或复习算法分析方法的本科生。通过文档可掌握规范的实验报告结构通过源码可加深对经典实现的理解是一份兼顾理论梳理与代码实践的学习资料。1. 算法分析与设计实验报告作业报告.zip这份压缩包到底该装什么才算合格只要学过计算机专业手里几乎都存过一个叫“算法分析与设计实验报告作业报告.zip”的文件。它可能是你期末的最后一关也可能是补考重修前的后悔药。这个 zip 里装的并不只是几份 Word 文档而是一套完整证据链你会不会做复杂度分析、能不能把伪代码变成能跑的程序、有没有跑出可靠数据。这篇博文我按自己给学生改作业时的验收标准来写从报告结构、代码复现、打包规范到避坑一步步带你把这份作业做成拿得出手的交付物。2. 实验报告的结构设计与复杂度分析先把理论部分写成可验收的文档2.1 五段式报告框架从问题描述到实验结论每一段的设计目的一份算法分析与设计实验报告最常见的翻车姿势是“有代码、没分析”。老师想看到的是你如何把一个具体问题抽象成输入和输出再一步步引到算法选型和复杂度推导上。我一般用自己的五段框架来写这也是我带研究生时反复强调的骨架段落核心内容常见硬伤问题描述输入格式、输出格式、数据规模约束把题目原文抄一遍没有任何抽象算法设计算法思想、伪代码、选它而不是别的算法的理由直接扔一段完整代码没有过程复杂度分析递推式、主定理或递归树推导、空间复杂度只写结论 O(n log n)跳步骤实验验证数据规模怎么设、怎么计时、图表展示图和代码对不上随机种子没固定结论理论推导与实测是否吻合、可改进点空话套话“算法效率很高”问题描述为什么要单独占一段因为它决定了你的算法设计有没有边界。比如 0-1 背包问题如果没有写明“背包容量 W 和物品数量 n 都属于正整数且 W 可以达到 10^5”后面你设计的动态规划数组大小就没有依据。这跟工程里写接口文档是一个道理先把输入输出的边界讲清楚再谈实现。算法设计这一段我强烈建议写伪代码而不是直接上真代码。伪代码能逼你先想清楚分支条件和循环不变量真代码容易陷入语法细节。比如归并排序的伪代码只需要四五行切分、递归、合并。到了作业代码那一章你再去把伪代码翻译成 Python 或 C这就是“先设计后编码”的完整闭环。2.2 用主定理与递归树完成复杂度推导两个必会做法复杂度分析是这份报告的门面。对形如 T(n) aT(n/b) f(n) 的递推式主定理是首选工具。这里 a 是子问题个数n/b 是每个子问题的规模f(n) 是分解和合并的代价。主定理把结果分成三种情况情况一若 f(n) 渐近小于 n^(log_b a)则 T(n) Θ(n^(log_b a))情况二若 f(n) 渐近等于 n^(log_b a)则 T(n) Θ(n^(log_b a) log n)情况三若 f(n) 渐近大于 n^(log_b a) 且满足正则条件则 T(n) Θ(f(n))。拿归并排序举例T(n) 2T(n/2) n。这里 a 2b 2n^(log_2 2) nf(n) n正好落在情况二所以 T(n) Θ(n log n)。报告里我会把 a、b、f(n) 这三个参数单独列一行再落结论。老师看的时候不用自己算就知道你是真懂了还是抄的结论。主定理不适用时就用递归树。比如 T(n) T(n/3) T(2n/3) n两个子问题规模不一样主定理套不了。画递归树每层合并代价都是 O(n)树高最坏到 log_{3/2} n叶子总量是 O(n^{log_3 2})最后整体还是 O(n log n)。报告里手绘一张递归树的图比写十行文字都有说服力。这部分是理论基础也是后面实验数据验证的对照物没有它你的实验数据就是一堆没有参照的散点。2.3 复杂度分析的一个必查参数输入规模 n 的设定与增长曲线理论推导完成后实验验证的第一步是定义 n 怎么取。我的习惯是固定两个参数数据规模序列用倍增从 100 到 3200 以 2 倍步长增长每个数据规模重复运行 5 次取最小值。为什么是倍增n 翻一倍时O(n log n) 的耗时大约翻 2 倍多一点O(n²) 的耗时翻 4 倍这个区分肉眼可见。如果你用 100、110、120、130 这样的小步长时间差异基本被噪声淹没画出来的曲线抖动严重谁看了都不会信。另一个参数是重复次数取最小值而不是平均值。平均值会被系统的后台进程、CPU 调度拖慢最小值最接近“无干扰运行时间”。这两点写进报告的实验设置里整个实验验证的可信度立刻上一个台阶。3. 作业报告的代码实现把伪代码变成可复现的算法程序3.1 用 Python 落地一个分治算法归并排序的完整实现与参数细节作业报告的代码部分我给的模板是“一个实验一个脚本脚本里只有算法核心和数据生成不掺 UI 和绘图”。以分治法最经典的归并排序为例最小可用版本长这样def merge_sort(nums): # 递归出口数组为空或只剩一个元素直接返回 if len(nums) 1: return nums mid len(nums) // 2 left merge_sort(nums[:mid]) right merge_sort(nums[mid:]) return merge(left, right) def merge(left, right): result [] i j 0 # 双指针比较左右两个子数组把较小的值依次放入结果 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 # 左右剩余元素直接拼接到末尾 result.extend(left[i:]) result.extend(right[j:]) return result逻辑说明merge_sort 先通过 mid len(nums) // 2 把数组切成两半分别递归排序最后调用 merge 合并两个有序数组。merge 里用 i 和 j 两个指针从两个子数组头部开始每次取较小值所以合并的整体操作次数和数组总长度成正比对应的就是递推式里那个合并代价 O(n)。两个参数细节需要特别注意一是 mid 用整数除法保证左边数组长度不小于右边或至多差 1二是合并时用 而不是 这样相同元素的先后顺序不会变满足稳定排序的要求后续在实验报告里可以顺带讨论稳定性对算法选型的影响。3.2 实验数据生成与计时数据规模、重复次数怎么设才有说服力代码能跑只是第一步能跑出可信数据才是作业报告的价值。我一般会把数据生成、排序和计时分三个函数写import random import time def bench(n, repeat5): # 生成 n 个 0~10000 之间的随机整数 data [random.randint(0, 10000) for _ in range(n)] times [] for _ in range(repeat): sample data[:] # 每轮用同一份数据的副本避免排序改变原数据 t0 time.perf_counter() merge_sort(sample) times.append(time.perf_counter() - t0) return min(times) # 取最小时间排除系统干扰 for n in [100, 200, 400, 800, 1600, 3200]: t bench(n) print(fn{n:6d}, min_time{t:.6f}s)参数说明random.randint(0, 10000) 生成的随机整数范围固定保证不同数据规模之间的数据分布一致repeat5 表示同一组数据跑 5 次取最小值time.perf_counter() 比 time.time() 精度更高在 Windows 和 Linux 上都能拿到纳秒级时钟。注意我刻意没有在 bench 函数里写 random.seed因为这里每轮用 data[:] 做副本数据本身在进入循环前已经固定不会因为排序被改变。你运行这段脚本时可以把输出重定向到文本文件这个文件就是报告里“运行结果”一节的原始证据。3.3 把运行结果和图表嵌进报告保证可复现的三个细节报告里贴图最容易翻车因为老师完全有可能重新跑一遍你的代码来核对。我给自己定的三条规矩缺一不可固定随机种子。random.seed(42) 放在脚本开头保证数据生成可复现保存原始输出。终端每次运行的时间戳不同我会把命令输出用重定向存成 txt和代码放在同一个目录图表横轴用对数刻度。n 从 100 到 3200 线性跨度太大直接用 plt.plot 会把小规模的数据全部挤到左边。绘图脚本我一般单独写一个不掺进算法脚本里import matplotlib.pyplot as plt plt.figure(figsize(6, 4)) plt.plot(sizes, times, markero) plt.xscale(log, base2) plt.xlabel(n (log scale)) plt.ylabel(time (s)) plt.title(Merge Sort Bench) plt.savefig(exp1_merge_sort.png, dpi150)这里 xscale(log, base2) 让横轴每一格正好代表 n 翻一倍配合上节说的倍增序列O(n log n) 和 O(n²) 的趋势差异一眼就能看出来。savefig 的 dpi150 保证图片放进 Word 或 Markdown 后仍然清晰如果 dpi 低于 100老师放大看细节时全是马赛克。这样代码、数据、图三者形成完整证据链任何一步都能反查。4. 把实验报告和代码打包成 zip目录规范与命令行操作4.1 zip 包的目录结构设计三个必留的顶层文件夹标题里的 zip 到最后才出场但它恰恰是很多人丢分的地方。我在收到学生作业时见过的乱象包括所有文件直接压在压缩包根目录、.c 文件和 .exe 文件混在一起、代码里还带着编译生成的临时文件。所以我要求压缩包内必须按这个结构组织algorithm_report/ ├── 01_实验报告/ │ ├── exp1_merge_sort.md │ ├── exp2_knapsack_dp.md ├── 02_作业代码/ │ ├── exp1_merge_sort.py │ ├── exp2_knapsack_dp.py ├── 03_运行结果/ │ ├── exp1_output.txt │ ├── exp1_merge_sort.png三个顶层文件夹各自承担一类角色实验报告是给人读的作业代码是给机器跑的运行结果是证明代码跑过的证据。序号 01_、02_、03_ 是为了让解压后的默认排序正好是阅读顺序先看报告再看代码最后看结果。这个细节在 Windows 的压缩文件夹里尤其重要因为资源管理器按文件名排序不按文件类型分组。我见过一份 45 分的作业交上来所有文件都摊在根目录文件名还叫“新建文档.docx”。老师连打开的兴趣都没有。目录结构就是交付礼仪zip 不只是打包工具它是你给别人留下的第一印象。4.2 用命令行创建和验证 zipzip/unzip 的常用参数Linux 和 macOS 上我不用图形化压缩工具直接用命令行干净且可重复。常见的做法是先把报告目录整理好再执行两行命令cd ~/algorithm_report_parent zip -rq algorithm_report.zip algorithm_report/ unzip -l algorithm_report.zip第一行的参数含义-r 表示递归压缩目录不加它 zip 只会把 algorithm_report 这个空目录放进去-q 表示安静模式不输出压缩过程里的逐文件信息否则文件一多屏幕刷满。第二行的 -l 是 list只列出压缩包内的文件清单而不解压用来确认文件结构是对的。如果发现缺文件或者路径不对趁此刻回头改目录而不是把整个包删掉重来。如果你用的是 Windows 且没装命令行 zipPowerShell 的 Compress-Archive 也能做到同样的事但有几个要注意的差异Compress-Archive 默认会带上顶层目录名解压出来会多一层嵌套它的压缩率通常比 zip 命令低而且中文文件名在跨平台解压时更容易出乱码。所以我在 Windows 上会优先要求装一个 Git Bash 或者用 Python 的 zipfile 模块目的只有一个让打包过程可复现、可检查而不是依赖鼠标右键。4.3 解压验证与伪加密交出去的包要能直接打开提交前最后一关我会用 Python 的 zipfile 做一个“冒烟测试”检查压缩包里有没有伪加密的文件。伪加密这个词经常和 zip 解压问题一起出现——有些压缩工具在写 zip 头部时把加密标志位设成 1但文件本体并没有实际加密解压软件看到标志位后要么弹密码框要么干脆拒绝打开。import zipfile with zipfile.ZipFile(algorithm_report.zip) as zf: for info in zf.infolist(): encrypted (info.flag_bits 0x1) 1 print(info.filename, encrypted if encrypted else plain)python3 check_zip.py代码说明infolist() 返回压缩包内每个文件的信息对象flag_bits 的低 1 位就是加密标志位。正常作业包这一位应该是 0如果你没设密码但打印出来是 encrypted说明这个 zip 是伪加密状态。处理办法是删掉这个文件重新打包或者用较新版本的工具执行“修复压缩包”操作。需要提醒的是网上流传的“zip 密码移除”工具对这个伪加密场景确实有一定效果但来路不明的工具的 DDL动态链接库风险远大于一个课程作业的价值我不建议任何人为了交作业去下载这类软件。伪加密本来就不用密码正常解压软件处理它只是标志位识别问题换用 Python 标准库的 zipfile 解压就能绕过去。注意一点检查脚本和打包脚本我都会存下来放在作业目录里证明这个包是经过验证的而不是随手右键压完就交。5. 算法实验报告避坑指南5 个高频踩坑记录与排查5.1 现象时间曲线不随复杂度走n 翻倍耗时却翻 4 倍以上原因分析最常被忽略的是计时范围里混入了数据生成或列表拷贝的时间。我在修改学生的作业时看到有人把 random.randint 放进计时段n3200 时数据生成占了近一半耗时画出来的曲线当然不匹配理论。另一个隐蔽原因是算法本身退化比如快速排序不随机选 pivot输入恰好接近有序时O(n log n) 直接退化 O(n²)。解决数据生成放在计时段外跑多次取最小值如果要对比两个算法必须保证喂给它们的是同一份数据副本。具体到代码就是把 data[:] 这份副样本传给被测函数而不是重新生成。5.2 现象RecursionError 递归深度报错程序直接崩溃原因分析Python 默认递归上限是 1000 层。归并排序深度是 log2 nn 到 10 万也只有 17 层基本不会爆但快速排序最坏情况下深度接近 n必爆。还有一个常见操作有些同学为了避免爆栈直接 sys.setrecursionlimit(100000) 一设了之结果内存被压爆程序闪退。解决能改迭代就改迭代快速排序可以用显式栈模拟递归如果坚持递归setrecursionlimit 是最后手段并且报告里要写明你用的是递归还是非递归实现。复杂度分析对应的实现方式不同递归版本的空间复杂度包含调用栈迭代版本则没有这一点不写清楚就是硬伤。5.3 现象报告里贴的运行截图和代码重新跑出来的结果对不上原因分析随机种子没有固定。数据一换时间、输出所有结果全部变化截图就成了“一次性的证据”。这是整个实验报告里最典型的黑匣子问题——老师代码还没看就知道你的证据链是断裂的。解决脚本第一行固定 random.seed(42)运行结果通过重定向保存为 txt 文件和代码、截图放在同一个目录。改用代码后重新生成结果不要让旧截图配新代码否则一旦被老师抽查到整份报告的可信度都会被打问号。5.4 现象解压 zip 时提示输入密码但同时没设过密码原因分析前面提过的伪加密。某些图形化压缩工具在打包时把加密标志位写进了 zip 头部但文件内容没有真正加密。跨平台解压时有的软件看到标志位就直接弹窗。还有一种情况是中文文件名的编码在 Linux 下无法解码被误认为解压失败。解决打包时统一用英文文件名报告正文用中文就可以提交前跑一遍第 4.3 节的标志位检查解压验证时用 unzip -l 先看文件清单再解压到临时目录。切记不要去下载来路不明的 zip 密码移除工具这类工具的安装包经常捆绑其他程序风险完全不值得承担。5.5 现象同一个作业老师和学生跑出来的时间差 3 倍以上原因分析机器配置、CPU 降频、后台进程调度都会影响绝对时间。如果你在报告里写“运行时间 0.03 秒优于 0.06 秒”而这两个数字来自不同机器或不同环境这句话在算法分析层面没有意义。解决报告里明确写出测试环境包括操作系统版本、Python 版本、CPU 型号比较算法只比较同一台机器上的相对增长趋势如果非要跨环境对比用“增长率比值”代替绝对时间。这一条是工程思维和课程实验思维的结合点写进报告是明显的加分细节。6. 从“能交差”到“加分项”报告验收的 3 个核心技巧技巧一是把复杂度分析写成“预测与实测对照表”。理论推导给出一组预测实验数据给一组实测两者同框展示基本不需要文字解释就能让老师认可。参考格式算法理论复杂度n1000 相对耗时预测n1000 实际耗时吻合情况归并排序O(n log n)1.001.00基准快速排序O(n log n)略低于归并0.82吻合插入排序O(n²)约 6.64 倍于归并7.10 倍吻合预测值基于 n log n 和 n² 在 n1000 时的比值比例实际耗时取 5 次最小。这个表我每次做实验一定会生成它让实验验证从“展示几张图”升级为“验证一个理论结论”。技巧二是用“最小值 标准差”代替单次运行时间。取最小时间是对“无干扰运行”的近似标准差能告诉读者数据本身稳不稳定。如果标准差超过平均值的 30%说明机器负载波动大这组数据本身就不可信应该换时间重测。技巧三是在结论里写清楚“数据规模再大时哪里先成为瓶颈”。比如归并排序的合并阶段是顺序访问缓存友好但数据大到无法装入内存时就变成外部排序问题动态规划 0-1 背包的空间复杂度 O(W) 在 W 很大时会先撑爆内存这时要考虑压缩状态数组。这个“可改进点”不需要你实现只需要证明你想到了——它往往是报告从 80 分到 95 分的关键。最后说一个我自己的经历。读研时交过一次全伪代码的作业老师顺着代码逐行查发现我少了递归出口直接在验收表上扣了一档。从那以后我养成了提交前不开任何多余程序的习惯先在干净的终端里把数据生成、排序、打包、解压完整跑一遍确认每一环都通才把 zip 交出去。这个动作多花十分钟但能帮你躲掉 90% 的返工风险。希望帮到你。本文还有配套的精品资源点击获取