程序片段时间复杂度分析：O(n log n) 解题思路

程序片段时间复杂度分析：O(n log n) 解题思路

代码片段：

int cnt = 0;
for(int i = 1;i <= n;i ++){
  for(int j = 1;j <= n;j += i){
    for(int k = 1;k <= n;k += j){
      ++ cnt;
    }
  }
}

时间复杂度分析：

该程序片段包含三个嵌套循环，需要分析每个循环的执行次数。

• 外层循环: 执行 n 次。
• 中层循环: 执行次数与 i 的值有关，当 i = 1 时，执行 n 次；当 i = 2 时，执行 n/2 次；以此类推，当 i = n 时，执行 1 次。因此，中层循环的总执行次数约为 n/1 + n/2 + n/3 + ... + n/n ≈ C1 * log n (其中 C1 为常数)。
• 内层循环: 执行次数与 j 的值有关，当 j = 1 时，执行 n 次；当 j = 2 时，执行 n/2 次；以此类推，当 j = n 时，执行 1 次。因此，内层循环的总执行次数约为 n/1 + n/2 + n/3 + ... + n/n ≈ C1 * log n (其中 C1 为常数)。

综合考虑三个循环的执行次数，该程序片段的时间复杂度约为 n * (C1 * log n) * (C1 * log n) ≈ C2 * n * log^2 n，其中 C2 为常数。

结论: 该程序片段的时间复杂度为 Θ(n log n)。

提示:

• 𝑛1 + 𝑛2 + 𝑛3 + ⋯ + 𝑛𝑛 ≈ 𝐶1 × log 𝑛
• 𝑛12 + 𝑛22 + 𝑛32 + ⋯ + 𝑛𝑛2 ≈ 𝐶2

其中，𝐶1, 𝐶2 均为常数。