时间复杂度 · 相关章节

复杂度分析是区分"会不会写"和"写得好不好"的分水岭。初赛考概念、复赛考直觉：一眼看出算法会不会超时，靠的就是本章的渐进分析与递推求解。

算法的复杂度是衡量算法效率的重要指标，主要包括时间复杂度和空间复杂度。时间复杂度用于描述算法执行所需的时间与输入规模之间的关系，空间复杂度则用于描述算法执行过程中所需要的存储空间与输入规模之间的关系。评估算法的复杂度是选择和优化算法的基础。

衡量一个算法"快不快、占不占内存"，靠的不是跑一次看秒表，而是渐进复杂度——即输入规模 $$n$$ 变大时，运行时间/内存如何增长。八级要求"能分析排序、查找、树图遍历、搜索、分治、动态规划等各类算法的时间和空间复杂度，并据此优化"。

复杂度估算是 GESP C++ 五级知识块 2 的独立考点：要求掌握算法复杂度估算方法，尤其含多项式（如 $O(n)$、$O(n^2)$）与对数（如 $O(\log n)$、$O(n\log n)$）的复杂度。本章补充分章，因为五级大纲把它与大整数、链表、二分、递归、分治、贪心并列为核心知识块，而前 8 章（41–48）未设专门章节。掌握复杂度，才能在选择算法时判断"会不会超时"。