求一个数x的n次方最朴素的方式是在1的基础上乘n次x,如果用递归,显然会执行n次递归函数,时间复杂度为O(N)。不过可以通过对n的奇偶性判断来加大递归步长,每次可将范围减半,即如果n是偶数,那么x^n = x^(n/2) * x^(n/2),下面的函数是实现了这个过程的完整代码,它的时间复杂度为()
int pow(int x, unsigned int n) { if (n == 0) return 1; if (n & 1) return pow(x, n / 2) * pow(x, n / 2) * x; else return pow(x, n / 2) * pow(x, n / 2); }