给出不同策略求两个数的最大公约数GCD(a,b)，并进行分析。
辗转相除法
辗转相除法（Euclidean algorithm）是一种用来求两个整数的最大公约数（Greatest Common Divisor，简称GCD）的算法。这个算法的基本思想是，用较大的数除以较小的数，然后用得到的余数去除较小的数，不断重复这个过程，直到余数为0为止。最后一次除法所得的非零余数即为这两个数的最大公约数。
伪代码：
给你一个整数数组
nums，返回数组中最大数和最小数的 最大公约数 。两个数的 最大公约数 是能够被两个数整除的最大正整数。
tips:c++可以直接调用gcd()函数哦~
class Solution {
public:
int gcd(int a,int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int findGCD(vector<int>& nums) {
auto x = max_element(nums.begin(), nums.end());
auto y = min_element(nums.begin(), nums.end());
return gcd(*x, *y);
}
};
分析：
辗转相除法是一种非常高效的算法，其时间复杂度主要取决于输入的两个整数的大小。假设输入的两个整数分别为 ( a ) 和 ( b )，且 ( a > b )，则其时间复杂度可以表示为
\[O(\log \min(a, b))\]辗转相除法的性能分析如下：
-
时间复杂度：在每一次迭代中，除法和取模运算的时间复杂度都是 $( O(\log n) )$，其中 ( n ) 是输入的两个整数中较小的那个数。因为每次迭代都会将问题的规模减小至原来的一半，所以总体的时间复杂度是 $O(\log \min(a, b) )$。
-
空间复杂度：辗转相除法的空间复杂度很低，只需要存储少量的变量，因此空间复杂度可以近似看作是常数级别的，即 $O(1)$。
-
最坏情况：辗转相除法的最坏情况发生在输入的两个整数的大小差异很大时，此时迭代的次数较多。但即便如此，其时间复杂度仍然是 $O(\log \min(a, b)) $，因为问题规模在每次迭代中都会减半。
-
最佳情况：最佳情况是输入的两个整数相等，此时只需一次迭代即可求得最大公约数，时间复杂度为 $O(1)$。
总体来说，辗转相除法是一种时间复杂度较低、效率较高的算法，适用于求解两个整数的最大公约数的场景。
质因数分解法
质因数分解法的原理是利用每个数唯一的质因数分解来找到两个数的最大公约数。它基于以下数论定理：
定理： 任何一个正整数 ( n ) 都可以唯一地表示为质数的乘积形式，即质因数分解。
根据这个定理，我们可以将两个数 ( a ) 和 ( b ) 分别分解为质因数的乘积形式：
$a = p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_m^{a_m} $ $b = q_1^{b_1} \times q_2^{b_2} \times \ldots \times q_n^{b_n}$
其中， $p_1, p_2, \ldots, p_m$和 $q_1, q_2, \ldots, q_n$是 ( a ) 和 ( b ) 的质因数， $a_1, a_2, \ldots, a_m$和 $b_1, b_2, \ldots, b_n$是它们对应的指数。
最大公约数 $\text{GCD}(a, b) $即为这两个数质因数分解中共同的质因数的乘积。也就是说，我们将两个数的质因数分解中共同的质因数相乘即可得到最大公约数。
这个方法是正确的，因为最大公约数实际上是两个数中能够整除它们的最大的数，而这个最大的数必然包含了两个数的所有共同质因数，因此质因数分解法可以正确地找到最大公约数。
代码：
#include <iostream>
#include <vector>
using namespace std;
// 函数：求一个数的质因数
vector<int> prime_factors(int n) {
vector<int> factors; // 存储质因数的向量
int divisor = 2; // 从最小的质数2开始试除
while (n > 1) {
while (n % divisor == 0) { // 若能整除，则将该质因数加入向量
factors.push_back(divisor);
n = n / divisor; // 更新n为除去该质因数后的商
}
divisor++; // 尝试下一个可能的质因数
}
return factors;
}
// 函数：求两个数的最大公约数
int gcd(int a, int b) {
vector<int> factors_a = prime_factors(a); // 求a的质因数
vector<int> factors_b = prime_factors(b); // 求b的质因数
vector<int> common_factors; // 存储两个数的公共质因数
for (int factor : factors_a) {
auto it = find(factors_b.begin(), factors_b.end(), factor);
if (it != factors_b.end()) { // 若该质因数同时存在于两个数的质因数中，则为公共质因数
common_factors.push_back(factor); // 将公共质因数加入向量
factors_b.erase(it); // 从b的质因数向量中移除该质因数，避免重复计算
}
}
int gcd_value = 1; // 初始化最大公约数为1
for (int factor : common_factors) { // 将公共质因数相乘得到最大公约数
gcd_value *= factor;
}
return gcd_value;
}
int main() {
int a, b;
cout << "Enter two integers: ";
cin >> a >> b;
int result = gcd(a, b);
cout << "GCD of " << a << " and " << b << " is " << result << endl;
return 0;
}
分析：
至于时间复杂度 $O(n)$ ，这是因为质因数分解的复杂度通常取决于较小的那个数的大小，而在较小的数范围内进行质因数分解的时间复杂度通常是 $O(\sqrt{n})$级别的，其中$n$是较小的那个数。