C++算法的复杂度？

Question

我写了以下代码:

class Solution {
public:
    int countPrimes(int n) {
        if (n==0 || n==1)
            return 0;
        int counter=n-2;
        vector<bool> res(n,true);
        for (int i=2;i<=sqrt(n)+1;++i)
        {
            if (res[i]==false)
                continue;
            for (int j=i*i;j<n;j+=i)
            {
                if (res[j]==true)
                {
                    --counter;
                    res[j]=false;
                }
            }
        }
        return counter;
    }
};

但找不到它的复杂性，根据我的计算，内部循环运行 n/2 + n/3 + ... + n/sqrt(n)

Answer 1

好的，让我们先尝试从您的公式中获取总和(我将使用您的约定命名变量):

现在，请注意 n 是总和中的常数，因此可以将其移到总和之外。

现在，我们有一部分是线性的，另一部分我们仍然需要估计，但是如果仔细观察，它与调和级数非常相似，实际上对于无穷大的 n 是调和级数 - 1。
它的增长率是众所周知的 ln(n) + 1。( https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)
因此，算法的复杂度为 n*ln(n)。
更新
Beta 答案有正确的结果(使用正确的起点)，我将保留上述答案，因为程序保持不变，答案，恕我直言，它仍然有用。