Foreach 循环中的嵌套 If 语句是否会以线性方式增加计算复杂性？

Question

我已经开始对我的解决方案进行运行静态代码分析，并注意到我的团队有一个部分的 "code complexity" 评分超出了图表。

我调查了一下，发现 15 层 嵌套 if 语句，外部有一个 foreach 循环，内部有 2 个嵌套层。

我熟悉大 O 表示法和字典查找的复杂性，与双 for (foreach) 循环相比，它变成了效率低下的多项式增加，而不是线性增加。

但是，这是否意味着 if 语句导致了任何真正的进一步复杂性？

或者问题真的只是另一个 foreach 中的 foreach 而 if 语句只是线性增加，就像一堆失败的 case 语句一样？

IE：只是 readability/maintainability 问题多于实际效率问题？

我意识到这表明可能有更好的算法来处理这里所做的事情，但我正在从 foreach 语句中的 if 语句中寻找对效率低下的数学理解，如果有的话一.

Answer 1

您可能正在研究圈复杂度。由于 if 语句的数量，您的代码可以参与的路径有很多。想象一棵树，根向下延伸，每个 if 语句都是根的分裂，它们在不同的方向分支。

会有很多单独的根路径！

Cyclomatic complexity is a software metric, used to indicate the complexity of a program. It is a quantitative measure of the number of linearly independent paths through a program's source code.

降低圈复杂度的一种方法是尽可能消除唯一路径的数量。

嵌套的 IF 语句可能会增加时间复杂度。

首先，嵌套的 for 循环会导致 O(N^2) 时间 complexity.It 实际上取决于那些 if 语句的性质。如果 if 语句是 O(1)，例如检查变量是否等于 int，它应该对您的运行时几乎没有影响。

for(Object1: Array1){
    for(Object2: Array2){
        if(Object1.number == 20){
            if(Object2.number = 10){
                ...
            }
        }
    }
}
O(N^2) Time Complexity

但是，如果这些 if 语句遍历集合以查找匹配项，它将为每个集合迭代添加额外的 O(N) 复杂度层。

for(Object1: Array1){
    for(Object2: Array2){
        if(Array3.contains(Object1)){
            if(Array4.contains(Object2)){
                ...
            }
        }
    }
}
O(N^4) or more Time Complexity

重要的是要查看每个 if 语句的时间复杂度。甚至有可能每个 if 语句都比 O(N) 差，这会对程序的性能产生负面影响。

Foreach 循环中的嵌套 If 语句是否会以线性方式增加计算复杂性？

Do Nested If Statements within Foreach loops add to Computation Complexity more than just linearly?

performance

big-o

nested

time-complexity

nested-loops