时间复杂度分析与递归，以新南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。

要求

1. 禁止使用循环：不得使用while、for、do循环或goto语句。使用这些结构的答案将不得分。

2. 禁止辅助函数：不得使用辅助函数。若使用，本题最多只能获得一半分数。（为什么？如果需要辅助函数，可能表明未完全理解递归，建议向导师寻求反馈！）

3. 测试用例：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)))，因为每次递归调用都会将问题规模至少减少一半。这种方法高效且简洁，完全符合题目要求，不使用任何循环结构或辅助函数。

如果需要COMP2521更多的资料：⁠⁠⁠⁠UNSW学习知识库（UNSW Study Wiki）