使用 Big-Θ 表示法的最坏情况运行时间

Question

我明白最里面的for循环是Θ(logn) 最外层的两个 for 循环是 Θ(n^2)，因为它是一个算术和。 if 语句是我的主要问题。有谁知道如何解决这个问题？

int tally=0;
for (int i = 1; i < n; i ++)
{
   for (int j = i; j < n; j ++)
   {
        if (j % i == 0)
        {
            for (int k = 1; k < n; k *= 2)
            { 
                tally++;
            }
        }
   }
}

Answer 1

编辑：
现在我注意到循环顺序：i 在 j.

之前

在这种情况下，对于给定的 i 值 j 从 i 到 n 不等，并且有 (n/i) 个成功的 if 条件。

所以程序会调用最内层的循环

n/1 +n/2+n/3+..+n/n

次。这是 harmonic series 的总和，它收敛于 n*ln(n)

所以内循环会执行n*log^2(n)次。

如您所写，两个最外层的循环提供 O(n^2) 复杂度，因此总体复杂度为 O(n^2 + n*log^2(n))，第一项覆盖第二项，即循环，最终总体复杂度为二次。

int tally=0;
for (int i = 1; i < n; i ++)
{  
   // N TIMES
   for (int j = i; j < n; j ++)
   {  
     //N*N/2 TIMES
        if (j % i == 0)
        {
         //NlogN TIMES
            for (int k = 1; k < n; k *= 2)
            { 
             //N*logN*logN
                tally++;
            }
        }
   }
}

旧答案（错误）

这种复杂性与 sigma0(n) function (number of divisors) and represented as sequence A006218 (Dirichlet Divisor problem)

的总和有关

我们可以看到对于不超过 n 的值，除数之和的近似值是

  n * ( log(n) + 2*gamma - 1 ) + O(sqrt(n))

所以循环计数器 j 的平均成功 if 条件数是 ~log(j)

使用 Big-Θ 表示法的最坏情况运行时间

Worst-case running time using Big-Θ notation

algorithm

big-o

code-analysis

analysis

使用 Big-Θ 表示法的最坏情况 运行 时间

Worst-case running time using Big-Θ notation

algorithm

big-o

code-analysis

analysis

使用 Big-Θ 表示法的最坏情况运行时间