找不到这段 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 的数组:时间和空间复杂度 O(log(n))。

第三个循环是一个嵌套循环，迭代 j 次，其中嵌套循环迭代 j 到 1 次，总共 >j * (j - 1)/2 次。此过程的时间复杂度为 O(log(n)^2)，并且主导了前面的阶段。

该函数的总体时间复杂度为O(log(n)^2)，而空间复杂度为O(log(n))。 p>