指数的时间复杂度

Question

 int aux(int n, int x) {
    while (x < n) {
        x *= x;
    }
    return x;
}

int func(int n) {
    return aux(n, 2);
}

为什么func函数的时间复杂度是O(log(log(n)))？

Answer 1

由于x是从2开始的，我们在每一步都平方，所以它遵循以下顺序：

2^(2^0), 2^(2^1), 2^(2^2), ..., 2^(2^k), 2^(2^k) * 2^(2^k) = 2^(2^(k + 1)) ...

只要 2^(2^k) <= n => 2^k <= log(n) => k <= log(log(n))

循环就会继续

Time complexity of exponentiation