最大公約數算法

• 師從
• 輾轉相除法（歐幾里得算法）
• • 時間復雜度
• 更相減損術（《九章算術》）
• • 時間復雜度
• 二分化更相減損術
• • 思路
  • 優化
  • 時間復雜度

師從

本篇是觀Vita君算法視頻后總結，他是bilibili一位小up主：小學生Vita君
正所謂“生乎吾后，其聞道也亦先乎吾，吾從而師之”，誠然如此。
【算法小知識】如何求最大公約數（上）
【算法小知識】如何求最大公約數（下）

輾轉相除法（歐幾里得算法）

int gcd1(int a, int b) {return b ? gcd1(b, a % b) : a; }

時間復雜度

O(logn)

更相減損術（《九章算術》）

int gcd2(int a, int b) {if (a == b) return a;return (a > b) ? gcd2(a - b, b) : gcd2(a, b - a); }

時間復雜度

O(n)

二分化更相減損術

int gcd3(int a, int b) {if (a == b) return a;if (a & 1) {if (b & 1) return (a > b) ? gcd3(a - b, b) : gcd3(b - a, a);//4）return gcd3(a, b >> 1);//3）}if (b & 1) return gcd3(a >> 1, b);//2）return gcd3(a >> 1, b >> 1) << 1;//1） }

思路

① a為偶數，b為偶數，gcd(a,b)=gcd(a/2,b/2)*2；
② a為偶數，b為奇數，gcd(a,b)=gcd(a/2,b)；
③ a為奇數，b為偶數，gcd(a,b)=gcd(a,b/2)；
④ a為奇數，b為奇數，a>b時，gcd(a,b)=gcd(a-b,b)， a<b時，gcd(a,b)=gcd(a,b-a)

優化

1）規避了性能較差的模運算；
2）改善了更相減損術的效率；
3）其中的位運算分別對速度優化
/a & 1，將a的二進制數與1進行與運算，實現a % 2；
/a >> 1，將a的二進制數右移一位，實現a / 2；
/a << 1，將a的二進制數左移一位，實現a * 2；

時間復雜度

O(logn)

總結

以上是生活随笔為你收集整理的两数的最大公约数算法基础及优化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。