次方的快速算法？
1 回答
HUH函數
TA貢獻1836條經驗 獲得超4個贊
整數次方可以用快速冪算法
譬如計算x^y,可以先算出x^(y/2)
然后再自乘一次，如果y是奇數，那就再額外乘一次y
對于x^(y/2)，我們仍用上述方法遞歸計算，可以得到logy復雜度的算法
以下是循環寫法，效率比遞歸寫法略高一些
int pow(int x,int y)
{
int ans=1;
while(y)
{
if(y)ans*=x;
x*=x;
y>>=1;
}
return ans;
}
添加回答
舉報
0/150
提交
取消