書上原文:求冪運算, 要計算X^N, 如果N為偶數, 那么X^N = X^(N/2) * X^(N/2) , 如果N為奇數, 那么X^N = X^(N/2) * X^(N/2) * X.例如: X^62次,算法將如下進行, 它只用到了9次乘法X^3=(X^2)X, X^7=(X^3)^2X, X^15=(X^7)^2X, X^31=(X^15)^2X, X^62=(X^31)^2顯然, 所需要的乘法次數最多是2logN.圖片:通過這個例子和一個前輩的指明, 我總結出X^N = ((((x^2)^2+1)^2+1)^2+1)...., 但是如果通過這個求出時間復雜度為2logN?
添加回答
舉報
0/150
提交
取消