内循环的时间复杂度

Question

谁能帮我计算一下内循环的时间复杂度？据我了解，外部的将是 O(n)。但是我不知道如何计算第二个里面发生的事情。

for (int i = 2; i < n; i++) {
    for (int j = 2; i * j < n; j++) {
}

Answer 1

内部循环运行s 从 2 到但不包括 n/i 次。您可以将其表示为 n/i - 2.

如果我们运行内部循环 n - 2 次（因为这是外部循环的次数运行s），我们得到以下总和：

(n/2 - 2) + (n/3 - 2) + ... + (3 - 2)

我有一种预感，但不记得这个系列总和为 log_e(n) * n 或类似值的 100%。所以在时间复杂度上，这就变成了O(log n * n).

Answer 2

对于“外循环”的每次迭代，内循环运行 n/i 次

因此，总复杂度为：

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

对于上面的右项，上限是ln(n)

因此，此代码的复杂度为 O(n log n)。

Answer 3

一旦 i * j ≥ n，即当 j = ceiling(n / i) ~ n / i 时，循环退出。从j=2开始，迭代次数为ceiling(n / i) - 1.

Time complexity of the inner loop