【信息科学与工程学】计算机科学与自动化——第三篇 计算理论基础05 计算数论01

计算数论算法全览算法名称算法的思想理论依据算法的数学表达式/定义算法的计算公式/定义算法特性时间复杂度空间复杂度适用类型优点缺点应用场景欧几里得算法通过辗转相除，利用余数逐步缩小问题规模基于等式gcd(a,b)=gcd(b,a mod b)的递归关系gcd(a,b)=gcd(b,a mod b)递归：1. 如果b=0，返回a2. 否则返回gcd(b,a mod b)确定性，简单高效，无需质因数分解O(log min(a,b))O(log min(a,b))（递归栈）或O(1)（迭代）整数最大公约数计算