询问含乘法条件的嵌套循环的时间复杂度

要分析的代码片段：

for (int i = 1; i <= n; i++) { 
    for (int j = 1; j * i <= n; j++) { 
        minHeap.offer(arr1[i - 1] + arr2[j - 1]); 
    } 
}

你给出的**O(n²)**确实是这段代码时间复杂度的一个有效上界，但我们可以进一步推导出更精准的渐近界，下面来一步步拆解：

1. 计算循环的总迭代次数 #

外层循环中i从1遍历到n，对于每个i，内层循环的j需要满足j*i <= n，也就是j的最大取值为floor(n/i)。所以总迭代次数是以下求和式：
$$\sum_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor$$
这是算法分析里的经典求和项，它的渐近复杂度为O(n log n)。简单解释下：这个求和近似于n乘以调和级数（1+1/2+1/3+...+1/n），而调和级数的增长速度是O(log n)，因此整体总迭代次数是n×log n的量级。

2. 加上堆操作的时间开销 #

每次循环都会执行minHeap.offer(...)，这个操作的时间复杂度是O(log k)，其中k是当前堆内的元素数量：

• 如果代码没有限制堆的大小，堆的元素总数最终会等于总迭代次数O(n log n)，此时每次offer的时间可以简化为O(log n)（因为log(n log n)与log n是渐近等价的）；
• 结合迭代次数，总时间复杂度即为：O(n (log n)²)。

3. 验证你给出的O(n²)上界 #

你提出的O(n²)完全正确，我们可以通过最坏情况推导这个上界：当i=1时，内层循环会执行n次，而其他i值对应的内层循环次数都不会超过n，因此总迭代次数必然不超过n×n=n²，完全符合Big-O上界的定义——只要存在某个常数C和足够大的n₀，当n≥n₀时，实际运行时间不会超过C×n²，这显然成立。

补充小细节 #

如果这段代码是用于求解两个数组元素和的Top-K问题，通常会限制堆的大小为k，此时offer操作的时间复杂度为O(log k)（若k为固定常数则为O(1)），总时间复杂度会进一步降低到O(n log n)。

内容的提问来源于stack exchange，提问作者somenickname