求m的n次方你会吗（优化时间复杂度）

题目

今天卷哥去一家国际厂面试，刚坐下打完招呼面试官就问了第一个问题。

卷哥心想这问的什么问题，过流程的吗？

面试官眉头紧皱：

看面试官的意思是对卷哥解法的时间复杂度不太满意，卷哥想了15分钟没想出来；

卷哥：卒

题解

正常循环求m的n次方，时间复杂度为O(n)。

假设m为3，n为9，公式为：3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 = 19683

提取重复内容( 3 * 3 ) 以 m² 为基础值，那平方次数为n/2 需要额外判断n为奇数偶数，奇数得到结果值*m为最终结果。

如果为奇数n则时间复杂度为O(n/2-1)，偶数n就是O(n/2)

代码如下：

    public int process(int m,int n){
        int index = n/2,rm = m*m,result = rm;
        for (int i = 0; i < index-1; i++) {
            result *= rm;
        }
        if (n % 2 != 0){
            result *= m;
        }
        return result;
    }
1
2
3
4
5
6
7
8
9
10

那还有没有时间复杂度更低的算法？

上面我们是固定的两个值缩减，效率固定了就是O(n/2)，我们再分析一下：求平方的m值是固定的，那我们能不能不固定两个值缩减，反正值固定，每一次平方后n/2这样对数的算法效率就很快了。

但是这种情况下如果有奇数n/2后则会漏掉一次平方的过程，所以如果n为奇数当前值就需要* m原始值一次。

代码如下：

    public int process(int m,int n){
        int r=1,base=m;
        while(n!=0){
            if(n%2 != 0)
                r*=base;
            base*=base;
            n/=2;
        }
        return r;
    }
1
2
3
4
5
6
7
8
9
10

步骤图：

最后r x base = 19683就等同我们上图余出来一个单个m值需要与结果值进行平方

这种方式的时间复杂度为O(logn)，相对时间复杂度更低。