急：两个2个算法题

来源：百度知道 编辑：UC知道 时间：2024/06/17 15:09:47
一个是应用分治策略的大整数乘法，
还有是应用STRASSEN方法求矩阵乘积，
求各位帮个忙，
11点前就要啊！！！~~~~~
各位大哥，有点敬业精神好不？
我要完整的程序啊~~~~

http://cache.baidu.com/c?word=%B7%D6%D6%CE%3B%B2%DF%C2%D4&url=http%3A//www%2E91tech%2Ecn/BBS/printpage%2Easp%3FBoardID%3D17%26ID%3D3582&b=0&a=91&user=baidu

http://cache.baidu.com/c?word=strassen&url=http%3A//www%2Eprogramfan%2Ecom/club/showbbs%2Easp%3Fid%3D78010&b=0&a=112&user=baidu

设计一个有效的算法，可以进行两个n位大整数的乘法运算
小学的方法：O(n2) 效率太低
分治法:
X=a2n/2+b
Y=c2n/2+d
XY=ac2n+(ad+bc)2n/2+bd
复杂度分析

T(n)=O(n2) 没有改进
为了降低时间复杂度，必须减少乘法的次数。为此，我们把XY写成另外的形式：
XY = ac 2n + ((a-c)(b-d)+ac+bd) 2n/2 + bd 或
XY = ac 2n + ((a+c)(b+d)-ac