设计至少两种不同算法求解x的n次幂,分析各算法时间复杂度

Question

设计至少两种不同算法求解x的n次幂,分析各算法时间复杂度

Answer 1

第一种：直接一个for循环将n个x相乘,时间复杂度明显是O(x)
第二种：利用递归（其实不是递归也行的）,举例2^9,那个变成2^4 * 2^5,2^4变成2^2 * 2^2,此时2^2只需算一次,即是求x^n,若n是奇数,则x^(n/2) * x^((n+1)/2),若是偶数,则t=x^(n/2),t*t,并且可通过备忘录方法,即定义一个数组,每计一次,把其存进数组,如2^2=4,那么array[2]=4,因为array[2]可能会出现多次,所以使用递归前先看一看该数组位是否为0,是则正常递归,不是则直接用那个数据不用递归了.时间复杂度是O(logn)