首页 > 代码库 > 分治算法——Karastsuba算法
分治算法——Karastsuba算法
分治(Divide and Conquer)算法:问题可以分解为子问题,每个问题是可以独立的解决的,从子问题的解可以构建原问题。
Divide:中间分、随机分、奇偶分等,将问题分解成独立的子问题
Conquer:子问题的解可以单独解决,从子问题的解构建原问题最终的解
Combine:每一步将子问题产生的解进行合并得到最终的解,合并的复杂度影响最终的算法时间复杂度
Karatsuba算法是在普通乘法算法的基础上进行的提升,使得最终的复杂度从O(n^2)变为了O(n^1.585),基本思想是将原问题的规模每次减小一般,并且每次解决三个子问题:
X = Xl*2n/2 + Xr [Xl 左侧n/2位数 Xr 右侧n/2位数]
Y = Yl*2n/2 + Yr [Yl 左侧n/2位数 Yr 右侧n/2位数]
XY = (Xl*2n/2 + Xr)(Yl*2n/2 + Yr) = 2n XlYl + 2n/2(XlYr + XrYl) + XrYr
XY = 2n XlYl + 2n/2 * [(Xl + Xr)(Yl + Yr) - XlYl - XrYr] + XrYr
XY = 22ceil(n/2) XlYl + 2ceil(n/2) * [(Xl + Xr)(Yl + Yr) - XlYl - XrYr] + XrYr从
从而得到最终的算法时间复杂度为T(n) = 3T(n/2) + O(n),得到T(n) = O(n^1.585)。算法的伪代码如下:
karatsuba(num1, num2) if (num1 < 10) or (num2 < 10) return num1*num2 /* calculates the size of the numbers */ m = max(size_base10(num1), size_base10(num2)) m2 = m/2 /* split the digit sequences about the middle */ high1, low1 = split_at(num1, m2) high2, low2 = split_at(num2, m2) /* 3 calls made to numbers approximately half the size */ z0 = karatsuba(low1,low2) z1 = karatsuba((low1+high1),(low2+high2)) z2 = karatsuba(high1,high2) return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)下面是使用C++具体实现的过程,如果直接使用整数类型实现,可能会发生溢出,因此使用输入的字符串表示,实际运算的过程将字符串转换为数组进行加、减、乘操作。先看最终的算法实现:
string Multiplicate(string x, string y) { int len = GetSameSize(x, y); if (len == 0) return 0; if (len == 1) return MultiplyString(x, y); int p = len % 2 == 0 ? len / 2 : len / 2 + 1; string Xh = x.substr(0, len / 2); string Yh = y.substr(0, len / 2); string Xl = x.substr(len / 2); string Yl = y.substr(len / 2); string P1 = Multiplicate(Xh, Yh); string P2 = Multiplicate(Xl, Yl); string P3 = Multiplicate(AddString(Xh, Xl), AddString(Yh, Yl)); return AddString( AddString( MultiplyPower(P1, 2 * p), MultiplyPower(MinusString(MinusString(P3, P1), P2), p) ), P2 ); }上述就是按照伪代码进行实现,但是使用了字符串的数字运算操作,包括字符串与数组的转换,数组加、减、乘,具体实现如下:
void StringToArray(string a, int *arr) { int n = a.size(); for(int i = 0; i < n; i++) arr[n - i - 1] = a.at(i) - '0'; } void ArrayToString(int *arr, int len, string & a) { for(int i = 0; i < len; i++) a += '0' + arr[len - i - 1]; } string DelPreZero(string a) { int zeros = 0; for (int i = 0; i < a.size(); i++) if (a.at(i) == '0') zeros++; else break; if (zeros == a.size()) return "0"; return a.substr(zeros); } void MultiplyArray(int a[], int la, int b[], int lb, int *arr) { int i; for (i = 0; i < la; i++) for (int j = 0; j < lb; j++) arr[i + j] += a[i] * b[j]; for (i = 0; i < la + lb - 1; i++) { arr[i + 1] += arr[i] / 10; arr[i] = arr[i] % 10; } } void AddArray(int a[], int la, int b[], int lb, int *arr) { int i; int len = la > lb ? lb : la; for (i = 0; i < len; i++) arr[i] += a[i] + b[i]; if (la > lb) { for (i = lb; i < la; i++) arr[i] = a[i]; for (i = 0; i < la; i++) { arr[i + 1] += arr[i] / 10; arr[i] = arr[i] % 10; } } else { for (i = la; i < lb; i++) arr[i] = b[i]; for (i = 0; i < lb; i++) { arr[i + 1] += arr[i] / 10; arr[i] = arr[i] % 10; } } } void MinusArray(int a[], int la, int b[], int lb, int *arr) //a must be bigger than b { int i; for (i = 0; i < lb; i++) arr[i] = a[i] - b[i]; for (i = lb; i < la; i++) arr[i] = a[i]; for (i = 0; i < la - 1; i++) { if (arr[i] < 0) { arr[i + 1]--; arr[i] = 10 + arr[i]; } } } string MultiplyString(string a, string b) { int m = a.size(), n = b.size(); int *arrA = new int[m]; int *arrB = new int[n]; StringToArray(a, arrA); StringToArray(b, arrB); int *arrC = new int[m + n]; for(int i = 0; i < n + m; i++) arrC[i] = 0; string rst; MultiplyArray(arrA, m, arrB, n, arrC); ArrayToString(arrC, m + n, rst); delete []arrA; delete []arrB; delete []arrC; return DelPreZero(rst); } string AddString(string a, string b) { int m = a.size(), n = b.size(); int *arrA = new int[m]; int *arrB = new int[n]; StringToArray(a, arrA); StringToArray(b, arrB); int i, len = m > n ? m : n; int *arrC = new int[len + 1]; for(i = 0; i < len + 1; i++) arrC[i] = 0; AddArray(arrA, m, arrB, n, arrC); string rst; ArrayToString(arrC, len + 1, rst); delete []arrA; delete []arrB; delete []arrC; return DelPreZero(rst); } string MultiplyPower(string a, int len) { for(int i = 0; i < len; i++) a += '0'; return DelPreZero(a); } string MinusString(string a, string b) { int m = a.size(), n = b.size(); int *arrA = new int[m]; int *arrB = new int[n]; StringToArray(a, arrA); StringToArray(b, arrB); string rst; int i, len = m > n ? m : n; int *arrC = new int[len]; for(i = 0; i < len; i++) arrC[i] = 0; MinusArray(arrA, m, arrB, n, arrC); ArrayToString(arrC, len, rst); delete []arrA; delete []arrB; delete []arrC; return DelPreZero(rst); }
主要是涉及到字符串与数组的转换中字符串在数字中是逆序的,进行数组运算时方便,同时对于数组间的减法,只支持a 大于b的减法,如果是a 小于b可以用b减去a后再取反即可。还有就是对数组的动态空间申请后,需要及时释放。
参考:
1.http://www.geeksforgeeks.org/divide-and-conquer-set-2-karatsuba-algorithm-for-fast-multiplication/
2.http://en.wikipedia.org/wiki/Karatsuba_algorithm#Pseudo_Code_Implementation
分治算法——Karastsuba算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。