Big-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的n由反复除以2.它迭代log ₂(n)次.

在它自己的结果上调用它确实会返回log ₂(log ₂(n))以进行额外的 log ₂(log ₂(n))迭代.到目前为止,复杂度为O(log(N))+ O(log(log(N)).第一项占第二项,总体复杂度为O(log(N)).

最后一个循环迭代log ₂(log ₂(n))次,该最后阶段的时间复杂度为O(log(log(N)),在初始阶段之前可忽略不计.

请注意,由于x在函数结束之前未使用g,因此不需要计算它,编译器可能会很好地优化此循环.

总的时间复杂出来为O(日志(N)) ,这是不一样的O(日志(日志(N)).

Answer 2

看起来像是log(n) + log(log n) + log(log n).

按顺序:第一次递归f(),加上第二次递归f()和for循环,因此最终复杂度为O(log n),因为忽略了较低阶项.