首页 > 试题广场 >

假设整数乘法运算时间复杂度为 O(1), 计算整数的 n 次

[问答题]

假设整数乘法运算时间复杂度为 O(1), 计算整数的 n 次幂( n>0), 最快算法的时间复杂度为 ____.

第一种:直接一个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)
发表于 2017-08-21 20:13:46 回复(1)
使用快速幂,O(logn)。
发表于 2018-03-31 23:47:13 回复(0)
使用左移
发表于 2017-07-12 16:23:04 回复(2)
O(logn)
发表于 2018-03-31 19:48:45 回复(0)
不是O(1)么
发表于 2017-09-12 17:43:17 回复(0)
o(n)
发表于 2017-09-01 23:42:10 回复(0)
二分思想。
发表于 2017-08-21 22:49:25 回复(0)
LOG2(N)
发表于 2017-08-21 16:09:23 回复(0)
加减乘除计算O(1)
发表于 2017-08-18 14:50:22 回复(0)
递归不是O(1)吗
发表于 2017-08-04 22:30:40 回复(1)
lgn
发表于 2017-07-11 19:07:23 回复(0)