c - C语言的简单时间复杂度

Question

你们能告诉我f3的时间复杂度是多少吗？我在想 sqrt(n).log(n) 但官方答案是 n。有什么想法吗？

#define PARTS 4

void f3(int n) {
    if (n < 4)
        return;

    for (int i = 0; i * i < n; i++)
        printf("%d", i);

    for (int i = 0; i < PARTS; i++)
        f3(n / PARTS);
}

Answer 1

复杂度取决于 printf 的复杂度:如果您可以假设 printf("%d",i) 的成本恒定，那么时间复杂度似乎为为O(N + k.sqrt(N))，其中 k=-1。由于 sqrt(N) 由 N 主导，因此可以简化为 O(N)。

        cost(4*N) = 4*cost(N) + sqrt(4*N)
4*N + k*sqrt(4*N) = 4*N + 4*k*sqrt(N) + 2*sqrt(N)
              2*k = 4*k+2
                k = -1

如果printf("%d",i)的复杂度为log(i)，考虑到转换产生的位数>i 以 10 为基数，整体复杂度更难评估:k.sqrt(N) 变为 k.log(N).sqrt(N)，仍然以N为主。