c - 大O小澄清

Question

就时间复杂度而言，O(log(log(n))) 实际上只是 O(log(n)) 吗？
您是否同意此函数 g() 的时间复杂度为 O(log(log(n)))？

int f(int n) {
    if (n <= 1)
        return 0;
    return f(n/2) + 1;
}

int g(int n) {
    int m = f(f(n));
    int i;
    int x = 0;
    for (i = 0; i < m; i++) {
        x += i * i;
    }
    return m;
}

Answer 1

函数 f(n) 通过重复除以 2 计算以 2 为底的 n 的对数。它迭代 log₂(n) 次。

根据自己的结果调用它确实会返回 log₂(log₂(n)) additional log₂(log₂(n)) 次迭代。到目前为止，复杂度为 O(log(N)) + O(log(log(N))。第一项支配第二项，整体复杂度为 O(log(N)) .

最后的循环迭代log₂(log₂(n))次，最后一个阶段的时间复杂度是O (log(log(N))，初始相前可忽略。

请注意，由于 x 未在函数 g 结束之前使用，因此不需要对其进行计算，编译器可能会将此循环优化为无。

总体时间复杂度为 O(log(N))，这与 O(log(log(N))不相同。