复杂度、规模与正确性
数据结构与算法基础#Python全栈#第五阶段#数据结构与算法基础#复杂度、规模与正确性约 953 字 · 3 分钟阅读
追问显示点击任意追问卡片可收起 / 展开
本阶段学习说明
整体培养方向： Python 全栈开发就业，按北京 10～20k 岗位所需能力逐步推进。
本阶段定位： 承接 Python 语法、对象和文件处理，学习选择数据结构、分析复杂度和解决常见编程题，提升业务代码的正确性与效率。
适用环境： Python 3；内置容器操作的复杂度应明确实现背景、平均情况和最坏情况，不能直接等同于实际运行时长。
考查目标： 能解释基本结构与算法，使用内置容器和标准库解决问题，识别边界条件，并用样例与规模实验验证方案。
题库结构： 100 道题，每题包含追问；结合基础原理、解题思路、编程任务和业务场景。本阶段提供题目，不包含参考答案。基础题优先掌握，链表、图、回溯与动态规划作为渐进训练，不以竞赛型难题作为全栈开发入门门槛。
答题约定： 先说明输入、输出与约束，再提出基础解法和优化思路；解释时间、额外空间及是否修改输入。使用内置函数时说明其作用，要求手写算法的题目不直接用对应库函数替代。复杂度通常以元素数量为规模；字符串比较、超大整数运算等必要时另行计入成本。
时间复杂度与空间复杂度分别描述什么？
追问 为什么同样复杂度的两个程序，实际耗时和内存仍可能不同？
O(1)、O(log n)、O(n)、O(n log n) 与 O(n²) 如何理解？
追问 输入规模增大十倍时，各类操作量大致如何变化？
最好、平均、最坏情况与摊还复杂度有什么区别？
追问 顺序查找、哈希查找与动态数组追加分别需要说明哪一种情况？
一个循环内再遍历完整列表，复杂度是多少？
追问 如果内层循环始终只执行十次，分析又有什么不同？
内层循环只遍历外层位置之后的元素，为什么仍可能是 O(n²)？
追问 如何通过求总比较次数解释，而不是只数代码有几层循环？
每次将搜索范围减半，为什么通常是 O(log n)？
追问 需要哪些访问与范围条件，才能保持这样的分析？
递归调用带来的额外空间如何分析？
追问 调用深度、分支数量和保留的局部对象分别影响什么？
代码中“只有一个循环”就一定是 O(n) 吗？
追问 循环内的成员查找、切片、排序或字符串拼接如何计入成本？
如何验证算法在空输入、单元素和重复元素下正确？
追问 正常样例之外，边界、异常和随机对照分别应该覆盖什么？
如何通过实验比较两个算法，而不是只测一次耗时？
追问 输入规模、数据分布、重复次数、计时范围与运行环境如何控制？