下面代码的时间复杂度是多少？

sum =0;

            for (int i=1; i<n; i++) {

              for (int j=1; j< n/i; j++) {

                sum = sum +j;

              }

            }

在上面的外循环中，变量i从 1 运行到 n，从而使外循环的复杂度为 O(n)。 这解释了nO(n logn) 复杂度的一部分。

但对于外部部分，当我们看到 j 从 1 运行到 n/i 时，这意味着每当 i 为 1 时，复杂度为n所以我想内部时间复杂度也应该是O(n).

使总时间复杂度为O(n*n)=O(n^2)。

您可以使用 Sigma 表示法执行以下操作：

H_{n-1} 是调和函数：

求调和级数的大O https://stackoverflow.com/questions/25905118/finding-big-o-of-the-harmonic-series