找不到这段 C 代码的时间复杂度？

Question

我很难弄清楚如何计算某些代码的时间复杂度。我知道Big O的基础知识，虽然我不能完全理解一般如何计算。

这是我无法解决的问题的示例。希望你能：

void f(int n) {
    int j, s;
    for (j = 0, s = 1; s < n; j++, s*=2)
        printf(“!”);
    double values[j];
    for (int k = 0; k < j; k++)
        values[k] = 0;
    while (j--)
        for (int k = 1; k < j; k++)
            values[k] += 1.0 / k;
}

运行几点钟了？我想要一个解释:)

Answer 1

第一个循环迭代log2(n)次，计算j，n最高位的顺序。复杂度 O(log(n)).

第二个循环初始化一个大小为 j 的数组：时间和 space 复杂度 O(log(n))。

第三个循环是嵌套循环迭代j次，嵌套循环迭代j到1次，总共j * (j - 1) / 2次。这个的时间复杂度是O(log(n)^2)，并且支配前面的阶段。

这个函数的整体时间复杂度是O(log(n)^2)，而space复杂度是O(log(n))。

找不到这段 C 代码的时间复杂度？

Cannot find the time complexity of this C code?

c

runtime

big-o

time-complexity