乘法可以看成n个a相加,那么所需要的时间为O(n),那么如何降低乘法的时间呢(降低为logn)?
埃及乘法算法就是一种,分为奇数和偶数,(例如计算n*a)偶数从1开始是a,然后1✖2,a+a以此类推,奇数的时候是从1开始先加上一个a以后跟偶数是一样的。
似乎先把两个乘数按大小排出来然后小的数在前面会更快
我的代码(递归格式借鉴)
#include <bits/stdc++.h>
using namespace std;
int r;
int mu(int n,int a)
{
if(n==1)
return r+a;
if(n%2)
r+=a;
return mu(n>>1,a+a);
}
main()
{
int a,b;
while(cin>>a>>b)
{
r=0;
int t1=max(a,b);
int t2=min(a,b);
cout<<mu(t2,t1)<<endl;
}
}
原文链接: https://www.cnblogs.com/baccano-acmer/p/9791476.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/283211
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!