用递推或递归求快速幂的时间复杂度

用递推或递归求快速幂的时间复杂度用递推或递归求快速幂的时间复杂度？？求解

递推

public static int FastPower(int a, int n, int mod)
{
    int res = 1;
    while (n > 0)
    {
        if ((n & 1) == 1)
        {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        n >>= 1;
    }
    return res;
}

递归

public static int FastPower(int a, int n, int mod)
{
    if (n == 0)
    {
        return 1;
    }
    int t = FastPower(a, n / 2, mod);
    if (n % 2 == 0)
    {
        return (t * t) % mod;
    }
    else
    {
        return (t * t % mod * a % mod) % mod;
    }
}

内容来源与ChatGpt4及newbing和百度：

快速幂是一种优化的指数运算算法，用于求幂运算的结果。递推和递归都可以用来实现快速幂算法，它们的时间复杂度都是O(logn)。

递推实现快速幂的思路是：将指数n转化为二进制形式，从低位到高位遍历二进制数，每遍历一位，将底数的幂次方乘上2，如果该位是1，则再乘上底数的该位次幂。

C#代码：

public static long Power(long x, long n)
{
    long res = 1;
    while (n > 0)
    {
        if ((n & 1) == 1)
        {
            res *= x;
        }
        x *= x;
        n >>= 1;
    }
    return res;
}

递归实现快速幂的思路是：将指数n转化为二进制形式，若n为偶数，则底数的幂次方等于将底数平方后指数除以2的幂次方，若n为奇数，则底数的幂次方等于底数乘以将底数平方后指数除以2的幂次方。

C#代码：

public static long Power(long x, long n)
{
    if (n == 0) return 1;
    if (n % 2 == 0)
    {
        long half = Power(x, n / 2);
        return half * half;
    }
    else
    {
        long half = Power(x, (n - 1) / 2);
        return x * half * half;
    }
}

祝您问题迎刃而解