我最近一直在解決一個問題，使用Recursion找到兩個數字的GCD/HCF。我想到的第一個解決方案如下所示。
long long gcd(long long a, long long b){
if(a == b) return a;
return gcd(max(a, b) - min(a, b), min(a, b));
}
我看到了其他人的解決方案，其中一種方法非常常見，如下所示。
long long gcd(long long a, long long b){
if(!b) return a;
return gcd(b, a % b);
}
這兩個程式的時間復雜度有什么區別？我如何優化前一個解決方案，我們怎么能說后一個解決方案比任何其他演算法都有效？
uj5u.com熱心網友回復：
這兩個程式的時間復雜度有什么區別？
如果您在談論時間復雜度，那么您應該考慮大 O 表示法。第一個演算法是O(n)，第二個是O(logn)，其中n = max(a, b)。
如何優化以前的解決方案？
事實上，第二種演算法是第一種演算法的直接優化。a在第一種解決方案中，如果和之間的差距b很大，則需要多次減法a - b才能達到余數a % b。所以我們可以通過使用整數模運算來改進這部分，從而產生第二種演算法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/495353.html
下一篇：及時預測圓到圓的交點