cumt算法设计与分析期末考速通笔记（1）｜复杂度分析

1 工作量函数与分析步骤 #

T(n)表示输入规模为n时的工作量函数。括号表示规模，不是乘法；T(n-1)表示规模缩小为n-1后的工作量。

分析步骤：确定输入规模 → 选择基本操作 → 统计执行次数或列递推式 → 求增长的阶。默认一次比较、赋值等基本操作耗时为常数。

对这些表达式，保留增长最快的项，忽略固定倍数和低阶项。

2 O Ω Θ #

所有固定倍数均要求为正，以下不等式只需在n足够大后成立。

例：T(n)=5n+10。n≥1时：

因此T(n)=O(n)，T(n)=Ω(n)，T(n)=Θ(n)。

上界可以给宽，紧确阶不能随意给宽。 5n+10也属于O(n²)，但不属于Θ(n²)。上界越贴近真实增长级别，分析越有价值。

上界不等于最坏情况，下界不等于最好情况。 最好、最坏、平均是在区分输入或随机运行情况；O、Ω、Θ是在描述选定函数的增长范围。

考试要求“求上界”用O，要求“求紧确阶”用Θ。一般问时间复杂度，给出尽量贴合增长级别的上界。

3 循环次数 #

单循环与嵌套循环 #

循环n次，每次固定操作：O(n)
外层n次，内层每轮固定3次：3n次，O(n)
外层n次，内层每轮n次：n²次，O(n²)

翻倍与减半 #

for (int i = 1; i < n; i *= 2) {
    // 固定工作量
}

n=8时i取1、2、4，共3次。2³=8，所以log₂8=3；一般循环次数约为log₂n，复杂度为Θ(log n)。

32 → 16 → 8 → 4 → 2 → 1
减半5次，因为2⁵=32。

不要只数循环层数 #

两层循环不必然是O(n²)。若内层指针i不重置、始终向后移动，全部外层循环合计最多推进n次，扫描仍可为O(n)。例见贪心专题的区间覆盖。

4 顺序执行相加 每轮执行相乘 #

两步先后执行，总耗时相加。例如排序后扫描：

n≥2时，n≤nlog₂n，因此nlog₂n+n≤2nlog₂n。

如果每次外层循环都完整执行一个n次内层循环，才会产生n×n次工作。

5 常用排序复杂度 #

一般数据的完整比较排序具有Ω(nlog n)下界。归并排序只是能保证最坏O(nlog n)的一种实现，不是所有排序题都必须用它。

特殊条件：已经按需要的关键字排序时可省略排序；关键字是小范围整数时，可考虑分桶或计数，时间O(n+U)，U为取值范围。

6 考场书写模板 #

设输入规模为n，分析基本操作的执行次数。
由循环或递归结构得到工作量表达式/递推式。
计算后保留主导项，给出O或Θ结论。
题目要求详细过程时，写出展开、求和或不等式。

递归题的完整推导见递归与分治专题。