复杂度预算与算法选型

本课目标

本课训练“复杂度预算与算法选型”。你需要产出可检查的复试材料，并能在追问下说明信息来源、技术机制、设计取舍与事实边界。

一、严格结论

算法选型应从约束反推允许的数量级，再比较时间、空间、实现风险和常数；大O是渐近上界，不等同实际秒数。

复试不是关键词背诵。任何结论都要区分已知事实、合理假设和个人判断；涉及院校安排时记录来源与日期，涉及技术结论时写清条件与失败边界，涉及个人经历时区分本人和团队贡献。

二、执行流程

估算最大操作次数，识别排序、哈希、双指针、动态规划或图搜索的候选；写出最坏情况和内存占用，再选最简单可通过方案。

练习时先限时作答并录音，再逐句标注：这一句回答了什么；证据是什么；若删除它是否影响结论。没有信息增量的套话应删去，缺少证据的强主张应降级或补证。

三、追问案例

n为十万时平方枚举通常不可行，可考虑排序加双指针或哈希；但若内存极严，哈希的额外空间可能不合适。

处理案例时采用“结论先行—机制展开—证据验证—边界收束”。面试官继续追问时，从当前答案的假设、复杂度、故障或替代方案展开，不突然切换到无关知识点。

四、本课产物

一张约束—候选算法—时间—空间—风险比较表。

产物必须能够在下一次模拟中直接使用，并保留版本与日期。完成后请让同伴只依据产物追问三轮；若第三轮只能靠猜测回答，就在文档中明确知识缺口与补课动作。

五、高风险误区

典型失分是：永远选择渐近复杂度最低但实现极易出错的方案。 纠正它的方法不是增加套话，而是补齐来源、条件、证据和个人责任边界。

六、在线验收

单选检查唯一严格结论，多选检查必要流程，应用问答要求把本课两个关键词用于具体案例。问答同时保存三层评分细则与参考作答，便于模拟面试后复盘。