此代码的大O时间复杂度

Question

for(int i = 1; i <= N; i++)
    for(int j = 1; j <= N; j = j+i)
    {
        //Do something
    }

我知道，对于ITH迭代，J递增CEIL(N/2(i-1))。

Answer 1

i的每个值的内循环的总迭代次数将为

i = 1: j = 1, 2, 3 ..., n ---> total iterations = n
i = 2: j = 1, 3, 5 ..., n ---> total iterations = n/2 if 2 divides n or one less otherwise
i = 3: j = 1, 4, 7 ..., n ---> total iterations = n/3 if 3 divides n or one less otherwise
...
i = m: j = 1, 1 + m, ... , n ---> total iterations ~ n/m
...
1

因此，大约总的迭代次数为(n+n/2+n/3...+1)。

该和是调和级数，其值近似为ln(n)+c，所以总迭代近似为nln(n)，由于所有对数都由一个常数相关，所以迭代将为o(nlogn)。