使用if语句为循环确定嵌套的三个循环中的big-O

Question

以下代码的big-O是什么：

y=1;
x=3;
for(int i =1 ; i < =n ; i*=2)
for(int j =1; j<= i * i; j++)
if (i % j == 0)
for(int k = 1; k<=j; k++) 
y=y*x;

我的想法：看看另一个类似的问题，我认为最内部的循环是O(n)，第一个循环是O(log (n))。。至于中间的O(n^2)

因此总体结果将是O(log(n)*n^3)

我的答案和思考方式正确吗？我是新手，所以我希望我能得到一些帮助来解释这个循环是如何工作的。

Answer 1

如果i % j == 0，则最内部的循环将运行j次。由于中间循环将运行i^2次，因此只有当j < i时，才有可能满足指定的条件。因此，在中间循环的i^2次迭代中，至少i^2 - i次，将不满足该条件。

假设我们用tau(i)表示i的除数，在j < i中，只有tau(i)倍的条件将满足，这意味着最内环的总复杂度等于最多为77/16 i的i的除数之和(见本文的证明(。

因此，中间环路与内部环路的总复杂度最多为(i^2 - i) + (i - tau(i)) + 77/16 i = i^2 + 77/16 i - tau(i)。

我们还知道tau(i)在O(i^(1/loglog(i)))中(见这里的证明(。现在，为了找到整个循环的复杂性，我们需要对i = 1, 2, 4, ..., n的最后一个表达式求和。由于我们希望找到渐近复杂度，并且这里有一个和，我们可以忽略i的下幂。因此，整个循环的时间复杂度为1 + 2^2 + (2^2)^2 + ... + (2^2)^log(n) = ((2^2)^(log(n)+1)-1)/(2^2-1) = Theta(n^2)(因子为2^2和log(n)项的几何和(。

总之，指定代码的较高时间复杂度分析是Theta(n^2)，它也在O(n^2)中。