问题描述 #

待分析代码 #

def is_prime(n):                        
    if n <= 1:                          
        return False                    
    if n == 2 or n == 3:                
        return True                     
    if n % 2 == 0 or n % 3 == 0:         
        return False                    
    i = 5                               
    while i * i <= n:                   
        if n % i == 0 or n % (i + 2) == 0:
            return False                
        i += 6                           
    return True                         

我用公式 M = 决策节点数 + 1 计算这段代码的圈复杂度，得到的结果是6；但当我画出控制流图（节点对应行号，带字母的节点比如4a、4b代表逻辑OR的两个条件），用公式 M = E - N + 2 计算时，结果却是5。为什么会出现这种差异呢？

控制流图说明：节点对应代码行号，带有字母后缀的节点（如4a、4b等）表示逻辑OR拆分出的两个子条件。

问题解答 #

咱们先拆解问题出在哪——两种计算方法的核心差异，其实是你对「决策节点」的定义理解，以及控制流图的绘制细节上出现了偏差。

1. 「决策节点+1」计算的误区 #

你得到6的结果，应该是把每个if/while语句直接算作一个决策节点：

• 行2的if n<=1 → 第1个决策点
• 行4的if n==2 or n==3 → 第2个决策点
• 行6的if n%2==0 or n%3==0 → 第3个决策点
• 行9的while i*i <=n → 第4个决策点
• 行10的if n%i==0 or n%(i+2)==0 → 第5个决策点
  5+1=6。但这个计数不符合圈复杂度的规则：复合条件中的逻辑运算符（OR/AND）会额外增加决策节点，因为每个逻辑运算符本质上是一个嵌套的分支判断。

比如行4的n==2 or n==3，实际是两个连续的决策：先判断n==2，为真则直接返回True；为假再判断n==3——这是两个独立的决策节点。同理，行6和行10的OR条件，每个都要拆成两个决策节点。

正确计数的话，决策节点总数是8个：

1. 行2：n <= 1
2. 行4：n == 2
3. 行4：n == 3
4. 行6：n % 2 == 0
5. 行6：n % 3 == 0
6. 行9：i * i <= n
7. 行10：n % i == 0
8. 行10：n % (i+2) == 0

代入公式得到：M = 8 + 1 = 9。

2. 控制流图「E-N+2」计算的偏差 #

你得到5的结果，大概率是控制流图的绘制或边/节点计数有误。根据你描述的控制流图规则（拆分OR子条件为带字母的节点），咱们重新计数：

• 节点数（N）：包括所有行号节点、拆分的OR子条件节点，以及一个统一的结束节点，总共17个（1,2,3,4a,4b,5,6a,6b,7,8,9,10a,10b,11,12,13, 结束节点）
• 边数（E）：统计所有分支边，包括内部跳转和指向结束节点的边，总共24条（比如1→2、2→3、2→4a、4a→5、4a→4b...12→9，再加上3/5/7/11/13→结束的5条边）

代入公式得到：M = 24 - 17 + 2 = 9，和「决策节点+1」的正确结果一致。

你得到5的原因，可能是绘制时没有拆分OR子条件，把带OR的if当成单一节点，或者漏数了部分边/节点，导致计算结果偏小。

总结 #

两种方法结果不一致的核心原因是：

• 你用「决策节点+1」时，错误地忽略了复合条件中逻辑运算符带来的额外决策点；
• 控制流图的绘制或计数没有完整体现所有分支逻辑。

这段代码的实际圈复杂度应该是9，两种方法在正确计数的情况下结果会统一。

备注：内容来源于stack exchange，提问作者Arsenic