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