以下嵌套依赖循环的时间复杂度是多少

Question

for(int i = 2; i < N; i ++)
    for(int j = 1; j < N; j = j * i)
        sum += 1

我得到了

我们可以进一步推广吗？

Answer 1

利用对数的代数恒等式，logᵢ(N) = log N/log i，所以我们可以将log N作为一个因数取出来，求和就是1/log i。将这个总和近似为 1/log x 的积分，我们可以渐近地得到它是 O(N/log N)，每个 Wikipedia。由于我们之前取出了一个log N的因子，乘以这个得到O(N)的最终结果。