算法分析与设计

Appearance

1.6 综合练习 ​

这一节不是"刷题"。它的目标是把第一章的五种判断动作合在一起：

  • 澄清问题
  • 验证正确性
  • 判断复杂度
  • 建立模型
  • 审查工具输出

提交练习时，不只交答案，还要交你的判断过程。一个答案如果说不清为什么成立，就还不算完成。

提交格式 ​

除非题目另有说明，每道综合题建议按下面格式提交：

text
问题规格：
- 输入：
- 输出：
- 约束：
- 边界约定：

我的判断：
- 方案：
- 正确性理由或反例：
- 时间复杂度：
- 空间复杂度：

工具协作记录：
- 我给工具的提示：
- 工具输出摘要：
- 我接受、修改或拒绝的理由：

这个格式不是为了增加文档，而是为了让你的判断能被别人检查。

基础练习 ​

练习 1.1：任务澄清三问 ​

把下面这个模糊任务改写成清晰规格：

帮我写一个自动分组功能。

要求回答：

  1. 输入是什么？至少列出 4 个字段。
  2. 输出是什么？是一组名单、若干小组，还是一个可解释的分组方案？
  3. 问题结构是什么？是在分配资源、匹配条件，还是排序优先级？
  4. 约束是什么？哪些条件必须满足，哪些只是尽量满足？
  5. 至少写出 3 个边界情况。

评分重点：是否把"自动分组"从一句话变成了可实现、可测试的规格。

练习 1.2：最小反例 ​

某工具给出下面判断：

判断一个人能否参加所有会议：先按开始时间排序，然后只要每个会议的开始时间都大于前一个会议的结束时间，就说明没有冲突。

请回答：

  1. 这个思路大体在解决什么问题？
  2. "大于"一定正确吗？
  3. 如果一个会议 10:00 结束，下一个会议 10:00 开始，是否冲突？请先写出你的边界约定。
  4. 在你的边界约定下，给出一个最小反例，或者说明为什么没有反例。

评分重点：是否先确认规格，再评价代码或规则。

练习 1.3：复杂度类比 ​

用生活场景解释下面三种增长方式，并各写一个代码形状：

增长方式生活场景代码形状
Θ(n)
Θ(n²)
Θ(log n)

要求：

  1. 生活场景要说明 n 表示什么。
  2. 代码形状不需要完整实现，但要能看出执行次数。
  3. 不能只写"一层循环/两层循环"，必须解释为什么执行次数是这个量级。

进阶练习 ​

练习 1.4：隐藏成本审查 ​

下面代码用于去掉重复名字：

python
def remove_duplicates(names):
    result = []
    for name in names:
        if name not in result:
            result.append(name)
    return result

请回答：

  1. 表面上有几层循环？
  2. 哪一行隐藏了额外工作？
  3. 最坏情况下，隐藏工作形成什么求和式？
  4. 时间复杂度是什么？
  5. 如果改用"见过的名字记录表"，时间和空间会怎样变化？

评分重点：是否能看见一行代码背后的真实工作量。

练习 1.5：建模卡 ​

把下面需求写成建模卡：

班级要订 30 份午餐，预算 900 元以内，至少 5 位同学需要素食，尽量让大家满意。

必须包含：

  1. 输出
  2. 输入字段
  3. 硬约束
  4. 目标
  5. 规模
  6. 至少 3 个边界情况

然后写一段提示词，让工具只审查你的模型，不写代码。提示词必须要求工具检查：

  • 歧义
  • 缺失边界
  • 硬约束和目标是否混淆

练习 1.6：审查工具输出 ​

假设你让工具根据练习 1.5 写代码。工具返回了一个方案：

先选择满意度最高的套餐，尽量多订；如果预算不够，再选择下一个满意度最高的套餐。

请审查这个方案：

  1. 它是否一定满足素食数量要求？
  2. 它是否一定满足库存限制？
  3. 它是否可能因为先选单价高的套餐，导致后面无法凑够 30 份？
  4. 构造一个小例子，让这个规则失败。
  5. 你会如何要求工具重新审查它自己的方案？

评分重点：是否能用反例攻击一个看似合理的规则。

挑战练习 ​

练习 1.7：第一章综合任务 ​

选择一个你熟悉的真实任务，例如：

  • 安排小组展示顺序
  • 从候选活动中选择周末计划
  • 为自习室安排座位
  • 从商品列表中找出符合条件的结果
  • 给一天的学习任务排优先级

完成以下内容：

  1. 写一张问题规格卡：输入、输出、约束、边界。
  2. 写一张建模卡：硬约束、目标、规模、表示方式。
  3. 给出一个最简单的基线方案。
  4. 分析它的时间复杂度和空间复杂度。
  5. 构造至少 3 个测试用例，其中至少 1 个是边界情况。
  6. 让工具给出一个实现或方案。
  7. 写一份审查记录：你接受、修改或拒绝了什么，理由是什么。

最终提交应包含一份简短结论：

text
我认为这个方案可以 / 不可以接受。
理由是：
1.
2.
3.
仍然不确定的是：

评分标准 ​

维度合格表现不合格表现
问题规格输入、输出、约束、边界清楚只有一句自然语言需求
正确性能给出反例或简短理由只说"看起来对"
复杂度能说明 n 是什么，并估算增长量级只背一个 O(...)
建模区分硬约束和目标把所有要求混成一句话
工具协作能审查工具输出并说明取舍直接复制工具答案

小结 ​

第一章真正要训练的是判断能力。

你不需要在第一章记住很多算法名字，但你需要形成一套工作习惯：

  • 先澄清问题，再写代码。
  • 先确认规格，再验证正确性。
  • 先估复杂度，再谈性能。
  • 先建模，再让工具实现。
  • 接受或拒绝工具输出时，要说得出理由。

下一章会进入数据结构。重点仍然不是"背接口"，而是理解不同结构适合什么约束、会带来什么代价。

上一节：1.5 建模

下一章：第2章 数据结构

新时代的算法课程