c++ - 时间复杂度(大O符号)是多少？

Question

我无法计算该程序的时间复杂度。

`const int n=1e6+5;
 int prime[n];
 void pre()
 {
    prime[1]=1;
    for(int i=2;i<n;i++)
    {
        if(!prime[i])
        {
            for(int j=2;i*j<n;j++)
            {
                 prime[i*j]=1;
            }
         }
     }
 }`

您能用大O表示法告诉此程序的时间复杂度是多少

Answer 1

对于外循环的每次迭代，内循环迭代与n/i成比例的次数。因此，迭代的总数类似于n/2 + n/3 + … + n/n。我们可以将n分解为n * (1/2 + 1/3 + … + 1/n)。我们认识到括号中的东西基本上是直到项n的谐波序列，并且谐波序列的部分和在n中具有对数渐近增长(请参阅Wikipedia here)。

因此，内部循环的迭代总数看起来像n * log(n)一样增加。内循环的每次迭代都会执行恒定的工作，而内循环的外部每次迭代都会进行恒定的工作。因此，我们获得了像a * n + b * n * log(n)这样的工作总量O(n log n)。

现在这可能有点草率，因为从技术上讲，这不是将两个数相乘的“免费”操作。如果我们忽略了这一点，并假设我们正在谈论的是现实的计算机，那么无论大小(固定大小的变量)如何，所有乘法都花费相同的时间，那么这很好。实际上，如果手动执行此操作，则可能需要考虑相乘的成本，该成本可能与数字大小的对数成正比。这可能会添加一个额外的对数术语，给出诸如O(n log^2 n)之类的内容。 YMMV。