网站有什么用,河北廊坊建筑模板厂家,安徽建设工程信息网网,网站建设公司擅自关闭客户网络最大公约数算法师从辗转相除法#xff08;欧几里得算法#xff09;时间复杂度更相减损术#xff08;《九章算术》#xff09;时间复杂度二分化更相减损术思路优化时间复杂度师从
本篇是观Vita君算法视频后总结#xff0c;他是bilibili一位小up主#xff1a;小学生Vita君…
最大公约数算法师从辗转相除法欧几里得算法时间复杂度更相减损术《九章算术》时间复杂度二分化更相减损术思路优化时间复杂度师从
本篇是观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);//4return gcd3(a, b 1);//3}if (b 1) return gcd3(a 1, b);//2return 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为奇数ab时gcd(a,b)gcd(a-b,b) ab时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)
