我知道最里面的 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++;
}
}
}
}
编辑：
现在我注意到循环顺序：i之前j。
在这种情况下，给定i值j从ito变化n并且有(n/i)成功的 if 条件。
所以程序将调用最内层循环
n/1 +n/2+n/3+..+n/n
次。这是谐波级数的和，它收敛到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) 函数的总和（除数）相关联，并表示为序列 A006218（狄利克雷除数问题）
我们可以看到，对于高达 n 的值的除数和的近似值是
n * ( log(n) + 2*gamma - 1 ) + O(sqrt(n))
所以循环计数器的成功 if 条件的平均数量j是~log(j)
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句