带有永远不会执行的条件的循环的复杂性

Question

如果我们得到一个只有一个条件的循环，而该条件永远不会执行，那么在这种情况下循环的复杂度 BigO 是多少？

我只是想知道时间复杂度是根据一行执行的次数还是算法完成的时间来考虑的。

这个问题可能看起来与代码无关，但这只是我解决问题的方法。 无论如何，我正在尝试找出这段代码的复杂性：

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;

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)).