时间复杂度分析与递归，以新南UNSW的COMP2521作业题为例
作者：Smooth（连接教育高级讲师）
首发于：UNSW学习知识库（UNSW Study Wiki）
创作时间：2025年3月5日
如何测度算法的时间性能？理论分析Theoretical Analysis
测度算法时间性能的两种方式：实证分析Empirical Analysis、理论分析Theoretical Analysis
for (int i = 0; i < n; i++)
每一个算法都由一些核心的原始操作（primitive operations）组成：赋值、函数调用、计算表达式、递增和递减
我们可以假设执行任意一个原始操作花费的时间都差不多
得到上面的代码一共执行了1+(n+1)+n次原子操作
如果一次原始操作耗时c，则整个算法花费时间为c(2n+2)
算法运行的时间与输入数据的规模呈正相关
当输入数据的规模越大时，越能反映算法之间的性能差距
一般只考虑在最坏情况时（Worst case）算法的性能（如必须跑完整个for循环才找到你想要的值）
时间复杂度（Time complexity）：算法运行所需要的时间，它是一个关于输入数据量的函数
渐进行为（Asymptotic Behaviour）:当输入规模n趋近于无穷大的时候，算法的复杂度的增长趋势
-
去除低阶项
-
去除常数系数
渐进符号：O、Ω、Θ
大O表示法（Big-Oh notation）:用于对算法的渐进行为进行分类，这也是通常表达时间复杂度的方式
Lab题目任务1：GCD（计算最大公约数）
这道题目的翻译是：
两个整数a和b的最大公约数（GCD）是能同时整除a和b的最大整数。例如，16和28的GCD是4，因为16=4×4且28=4×7，没有比4更大的整数能同时整除两者。
虽然可以通过完全分解两个数并寻找公共因数来计算GCD，但这里有一个更快速简便的方法。
当我们用a除以b得到余数r时，a和b的公约数完全等同于b和r的公约数。因此，以下等式成立：
gcd(a, b) = gcd(b, r)
如果我们从任意两个正整数开始，并重复应用此等式，最终余数r会变为0，此时这对数中的另一个数即为最大公约数。
这种神奇的方法被称为欧几里得算法，可能是已知最古老的非平凡算法，最早记载于公元前300年左右的《几何原本》。
你的任务是在gcd.c中实现以下函数：
int gcd(int a, int b);该函数需使用上述欧几里得算法计算两个整数的GCD。你可以假设a和b是非负数，且最多其中一个为0。
要求
-
禁止使用循环：不得使用
while、for、do循环或goto语句。使用这些结构的答案将不得分。 -
禁止辅助函数：不得使用辅助函数。若使用，本题最多只能获得一半分数。（为什么？如果需要辅助函数，可能表明未完全理解递归，建议向导师寻求反馈！）
-
测试用例：
gcd.c包含一个main函数用于测试。程序通过命令行参数接收两个整数，例如：./gcd 16 28 # 输出：The GCD of 16 and 28 is 4 ./gcd 0 42 # 输出：The GCD of 0 and 42 is 42
解题思路：
-
递归终止条件：当第二个数
b为零时，返回第一个数a作为结果。 -
递归步骤：如果
b不为零，递归调用gcd(b, a % b)。这里a % b是a除以b的余数。
这种方法避免了显式的循环结构，完全依赖递归调用来不断减少问题规模，直到满足终止条件。
解决代码
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}该算法的时间复杂度是 O(log(min(a, b)))，因为每次递归调用都会将问题规模至少减少一半。这种方法高效且简洁，完全符合题目要求，不使用任何循环结构或辅助函数。