次方的快速算法？
1 回答
HUH函數(shù)
TA貢獻(xiàn)1836條經(jīng)驗(yàn) 獲得超4個(gè)贊
整數(shù)次方可以用快速冪算法
譬如計(jì)算x^y,可以先算出x^(y/2)
然后再自乘一次，如果y是奇數(shù)，那就再額外乘一次y
對(duì)于x^(y/2)，我們?nèi)杂蒙鲜龇椒ㄟf歸計(jì)算，可以得到logy復(fù)雜度的算法
以下是循環(huán)寫(xiě)法，效率比遞歸寫(xiě)法略高一些
int pow(int x,int y)
{
int ans=1;
while(y)
{
if(y)ans*=x;
x*=x;
y>>=1;
}
return ans;
}
添加回答
舉報(bào)
0/150
提交
取消