两种约数个数计算函数的时间复杂度与效率对比

问题背景 #

现有两个实现正整数约数个数计算逻辑的C函数：

• 第一个函数代码行数更少，计算数值500000的约数时需要执行250001次迭代
• 第二个函数代码行数稍多，同计算场景下仅需执行约800次迭代
  需要从时间复杂度维度判断二者的执行效率高低。

函数实现代码 #

// 第一个函数
int divisors(int n) 
{
  int i, count = 1;
  
  for (i = 1; i <= n / 2; i++) 
  {
    if (n % i == 0)
      count ++;
  } 
  
  return count;
}


// 第二个函数
int divisors(int nbr)
 {
    int div_1=1;
    int div_2=0;
    int n_div=0;
    
    
    do {
        
        if (nbr % div_1 == 0)
        {
            div_2 = nbr / div_1;
            if(div_1==div_2)
            {
                n_div+=1;
            }
            else
            { n_div+= 2; }
        }
        div_1 ++;

    }while(div_1<div_2);

    return n_div;
}

评估结论 #

第二个函数的执行效率显著高于第一个函数，二者时间复杂度不在同一量级：

• 第一个函数的循环终止条件为i <= n/2，迭代次数随输入值n线性增长，时间复杂度为O(n)。当输入n=500000时，循环需要从1遍历到250000，迭代次数达到25万级，输入值越大，迭代次数会同比例上涨。
• 第二个函数利用了约数成对出现的数学性质：若d是n的约数，则n/d必然也是n的约数，循环仅需要遍历到√n的位置即可终止，时间复杂度为O(√n)。对于n=500000，√500000≈707，加上边界判断的少量迭代，总次数就在800次左右，和实测结果匹配。同时代码中对完全平方数的中间约数做了去重处理，计数逻辑准确。

注：代码行数多少和执行效率没有必然关联，时间复杂度是衡量算法随输入规模增长时性能表现的核心指标。

内容的提问来源于stack exchange，提问作者MrFeli45