hmm 算法代码示例

Given two integers a and n, write a function to compute a^n.

给定两个整数a和n，编写一个计算a ^ n的函数。

码 (Code)

Algorithmic Paradigm: Divide and conquer.

算法范式：分而治之。

int power(int x, unsigned int y) {     if (y == 0)         return 1;     else if (y%2 == 0)         return power(x, y/2)*power(x, y/2);     else        return x*power(x, y/2)*power(x, y/2); }

Time Complexity: O(n) | Space Complexity: O(1)

时间复杂度： O(n) | 空间复杂度： O(1)

优化的解决方案：O(登录) (Optimized Solution: O(logn))

int power(int x, unsigned int y) {     int temp;     if( y == 0)         return 1;     temp = power(x, y/2);     if (y%2 == 0)         return temp*temp;     else        return x*temp*temp; }

Why is this faster?

为什么这样更快？

Suppose we have x = 5, y = 4, we know that our answer is going to be (5 * 5 * 5 * 5).

假设我们有x = 5，y = 4，我们知道答案将是(5 * 5 * 5 * 5)。

If we break this down, we notice that we can write (5 * 5 * 5 * 5) as (5 * 5) * 2 and further, we can write (5 * 5) as 5 * 2.

如果将其分解，则会注意到我们可以将(5 * 5 * 5 * 5)写为(5 * 5)* 2，然后，我们可以将(5 * 5)写为5 * 2。

Through this observation, we can optimize our function to O(log n) by calculating power(x, y/2) only once and storing it.

通过此观察，我们可以通过仅计算一次power(x，y / 2)并将其存储来将函数优化为O(log n)。

模幂 (Modular Exponentiation)

Given three numbers x, y, and p, compute (x^y) % p

给定三个数字x，y和p，计算(x ^ y)％p

int power(int x, unsigned int y, int p) {     int res = 1;      x = x % p;     while (y > 0) {          if (y & 1)             res = (res*x) % p;           // y must be even now         y = y >> 1;         x = (x*x) % p;       }     return res; }

Time Complexity: O(Log y).

时间复杂度： O(Log y) 。

翻译自:

hmm 算法代码示例