这个条件可以改变复杂性吗？

Question

我正在尝试找出这段代码的复杂性：

int count =0;
for(int i= 1 ; i<=MAX_SIZE ; i*=2){
    for(int j = 1; j<=i*i ; j++){
        if(i%j==0){
            for(int k = 1 ; k<=j ; k++)
                count++;
        }
    }
}
cout<<count<<endl;

外层循环是 O(log(n))
中间的循环是 O(n^2)
内循环的复杂度为 O(n)，原因如下：

内循环执行O(j)，即i*i，这是正确的。 但只有当 i%j == 0 时，该条件才会执行，并且当该语句为真时，意味着 j 必须小于或等于 i。
证明：

int count =0;
int count2 = 0;
for(int i= 1 ; i<=10000 ; i*=2){
    for(int j = 1; j<=i*i ; j++){
        if(i%j==0){
            if(i>=j)
            {
                count2++;
            }
            count++;
        }
    }
}
cout<<count<<endl;
cout<<count2<<endl;

如果您运行此命令，您将获得两个计数器的相同数字。 所以条件成立后 j 的最大大小是 i。 这意味着内部循环将运行 O(i) = O(n)

这给我们留下： O(log(n)).n^2.n) = O(log(n).n^3)
这是正确的吗？

好吧，现在讨论真正的问题，如果我尝试为多个值运行此代码，我会得到：

MAX_SIZE = 1000 , count = 2036  
MAX_SIZE = 10000 , count = 32752  
MAX_SIZE = 100000 , count = 131054  
MAX_SIZE = 1000000 , count = 131054  
MAX_SIZE = 10000000 , count = 131054  
MAX_SIZE = 100000000 , count = 131054  
.
.
.

对于 10000 之后的同一个数字，它会这样继续下去，我只是想知道我是否遗漏了一些东西，它的复杂度可能是 O(n) 吗？为什么？

Answer 1

1.外循环： 当 i 小于或等于 MAX_SIZE 时，循环进行迭代，并且在每次迭代中，i 都会加倍 (i *= 2)。这是一个几何级数，迭代次数将是相对于 MAX_SIZE 的对数。外层循环的时间复杂度为O(log(MAX_SIZE))。

2.中循环：中循环在每次外循环迭代中迭代 i * i 次。因此，中间循环的时间复杂度为O(i^2)。

3.最内层循环：最内层循环在每次中间循环迭代中迭代j次。所以，最内层循环的时间复杂度是O(j)。

将它们放在一起，所提供代码的总体时间复杂度是三个嵌套循环的时间复杂度的乘积：

� （ 日志 u2061 （ 最大尺寸 ） ⋅ 我 2 ⋅ j ） O(log(MAX_SIZE)·i 2 ⋅j)

现在，需要注意的是，中间循环中的条件 i % j == 0 意味着最内层循环仅在 j 是 i 的约数时执行。对于不同的 i 值，整体时间复杂度将受到 j 范围内除数分布的影响。

综上所述，时间复杂度通常是根据主导项来表达的，在这种情况下，外层循环主导了整体时间复杂度，最终的复杂度为 � （ 日志 u2061 （ 最大尺寸 ） ） O(log(MAX_SIZE)).