算法设计------计算a的n次方

发表于 | 分类于

数学公式归纳

递归实现

1
2
3
4
5
6
double pow (double a, int n){
    if (n == 0) return 1;
    if (n == 1) return n;
    double t = pow(a, n/2);
    return t * t * pow(a, n%2);
}

非递归实现

1
2
3
4
5
6
7
8
double pow (double a, int n){
    double ret = 1;
    while (n) {
        if (n%2 == 1) ret *= a;
        a *= a; n /= 2;
    }
    return ret;
}

时间复杂度

O(㏒ n)

如果对你有帮助的话，Star✨下一吧！