h****3 发帖数: 421 | 1 题目,写一个function 计算两个数的power,
float power (float x, int y) { }返回x^y.
请问怎么能使复杂度为O(lgn).
谢谢 | t*****g 发帖数: 1275 | 2 作lg(y)遍x*=x; 最后剩的补一下。
【在 h****3 的大作中提到】 : 题目,写一个function 计算两个数的power, : float power (float x, int y) { }返回x^y. : 请问怎么能使复杂度为O(lgn). : 谢谢
| k****f 发帖数: 3794 | 3 x
x*x --> x^2
x^2*x^2 --> x^4
x^4*x^4 --> x^8
按照y的二进制位,把对应x^(2^n)形式的数相乘
就是x^y
【在 h****3 的大作中提到】 : 题目,写一个function 计算两个数的power, : float power (float x, int y) { }返回x^y. : 请问怎么能使复杂度为O(lgn). : 谢谢
|
|