这个 power() 函数的复杂性是什么？

Question

这是求给定数的幂的算法。如果有的话，递归之后的语句将如何影响复杂性？

int power(int b, int n){
 if (n == 0)
    return 1;
 else {
    int p = power(b, n/2);
    if (n % 2 == 0) 
        return p * p;
    else 
        return b * p * p;
 }
}

Answer 1

因为，您在每一步将 n 除以 2，算法将运行直到 n 达到 0。我们可以看到发生了什么：

n1 = n / 2
n2 = n1 / 2 = (n / 2) / 2 = n / 4 = n / (2^2)
n3 = n2 / 2 = n / 8 = n / (2^3)
...
...

它的运行时间与 n >= (2^x) 一样长，其中 x 是任何 non-negative 整数。

所以，我们可以说，当 2^x > n 时，它停止（其中 x 是可能的最小整数，2^x > n）。

现在，我们可以写

2^k = n, // where k is a non-negative integer
or, lg(2^k) = lg(n) // here, 'lg' means 2-based log
or, k = lg(n)

因此，x(for which it stops running) 的最小可能值为 k + e, where e is a very small number，但当然，我们正在考虑 integer here(cause, no of steps)。所以，我们可以写 x = k + 1.

因此，算法运行的步数为 x（考虑到乘法的复杂性常数）等于 k + 1 或 lg(n) + 1。

所以，它是 O(lg(n) + 1) 或者，我们可以说，O(lg(n))。

这个 power() 函数的复杂性是什么？

what is the complexity of this power() function?

c++

algorithm

complexity-theory