c - 平方求幂的时间复杂度是多少？

Question

这是一个代码，用于对给定的数进行幂运算:

#include <stdio.h>

int foo(int m, int k) {
    if (k == 0) {
        return 1;
    } else if (k % 2 != 0) {
        return m * foo(m, k - 1);
    } else {
        int p = foo(m, k / 2);
        return p * p;
    }
}

int main() {
    int m, k;
    while (scanf("%d %d", &m, &k) == 2) {
        printf("%d\n", foo(m, k));
    }
    return 0;
}

如何计算函数 foo 的时间复杂度？

我已经能够推断如果k 是2 的幂，时间复杂度是O(log k)。

但我发现很难计算 k 的其他值。任何帮助将不胜感激。

Answer 1

How do I calculate the time complexity of the function foo()?

I have been able to deduce that if k is a power of 2, the time complexity is O(logk).

首先，我假设每个函数调用所需的时间是恒定的(例如，如果乘法所需的时间取决于要相乘的数字，则情况并非如此 - 在某些计算机上就是这种情况)。

我们还假设k>=1(否则，函数将无限运行，除非发生溢出)。

让我们将值 k 视为一个二进制数:

如果最右边的位是0(k%2!=0 为假)，数字右移一位(foo(m, k/2)) 函数被递归调用。

如果最右边的位是1(k%2!=0 为真)，则该位变为0(foo(m,k-1)) 并且函数被递归调用。 (我们还没有考虑 k=1 的情况。)

这意味着该函数为每个位调用一次，并且为每个 1 位调用一次。或者，换句话说:它为数字中的每个 0 位调用一次，为每个 1 位调用两次。

如果N是函数调用的次数，n1是1的位数，n0是0 位数，我们得到以下公式:

N = n0 + 2*n1 + C

常量C(C=(-1)，如果我没记错的话)表示情况k=1到目前为止我们都忽略了这一点。

这意味着:

N = (n0 + n1) + n1 + C

并且 - 因为 n0 + n1 = floor(log2(k)) + 1:

floor(log2(k)) + C <= N <= 2*floor(log2(k)) + C

如您所见，时间复杂度总是O(log(k))