数据结构与算法复杂度追问

本课目标

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

一、严格结论

算法回答必须区分操作、数据分布和复杂度口径；平均、最坏、摊还复杂度不能互换，空间复杂度也应说明是否计入输入。

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

二、执行流程

先说明数据结构不变量，再分析核心操作怎样维护不变量；复杂度从执行次数推导，最后给退化输入和替代方案。

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

三、追问案例

回答哈希表查询不能只说O(1)，应指出平均假设、冲突处理、负载因子和最坏退化，并比较平衡树在有序遍历与最坏保证上的优势。

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

四、本课产物

一张含操作、不变量、平均/最坏复杂度和退化条件的比较表。

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

五、高风险误区

典型失分是：把大O当作实际运行时间，或只背最优复杂度。 纠正它的方法不是增加套话，而是补齐来源、条件、证据和个人责任边界。

六、在线验收

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