请求分析嵌套循环代码的时间复杂度及计算步骤

待分析代码 #

for (i=1; i<=n; i++) {     
    for (j=1; j<=n; j=j+i) {         
        printf("x");     
    } 
}

时间复杂度结论 #

这段代码的时间复杂度为 O(n log n)。

具体计算步骤 #

1. 统计内层循环执行次数：外层循环每取一个i值，内层循环的j从1开始，每次递增i，直到j > n时停止。所以对于每个i，内层循环执行的次数是⌊n/i⌋（向下取整，比如i=1时执行n次，i=2时执行n/2次，直到i=n时执行1次）。
2. 计算总执行次数：把所有内层循环的次数加起来，总次数等于：

   n/1 + n/2 + n/3 + ... + n/n
   

   提取公因子n后，式子变为：

   n * (1 + 1/2 + 1/3 + ... + 1/n)
   

3. 调和级数的渐近行为：括号里的部分是调和级数，当n足够大时，这个级数的近似值为ln(n) + γ（γ是欧拉常数，约0.5772），它的渐近增长速度是O(log n)。
4. 推导最终复杂度：总执行次数的数量级就是n * O(log n)，因此这段代码的时间复杂度是O(n log n)。

内容的提问来源于stack exchange，提问作者Manar Ali Ahmed