如何计算质因数分解递归函数的时间复杂度及单独递归部分复杂度

原实现代码 #

void prime_factor(int n){
  if(n>1){
      int i= 2;
      while(n%i!=0){
          i++;
      }
      a[j] = i;
      j++;
          
      prime_factor(n/i);
  }
}

整体时间复杂度计算 #

结合算法逻辑可以分场景推导：

• 最好场景：当n为2的幂时，每次while循环只要判断1次就能找到最小质因数2，总共需要递归log2(n)次，每次非循环操作都是常数复杂度，整体时间复杂度为O(log n)
• 最坏场景：当n本身是质数时，while循环需要从i=2遍历到i=n才能找到整除的因子，循环执行n-1次，后续递归调用prime_factor(1)直接返回，整体时间复杂度为O(n)，和你已知的结论一致
• 普通场景：如果n是合数，它的最小质因数一定不大于√n，因此首次while循环最多遍历√n次，后续递归处理更小的n/i，整体复杂度优于O(n)

仅递归部分的复杂度 #

「仅递归部分」默认排除while循环的执行耗时，仅统计递归调用、数组赋值、下标自增这些常数操作的总耗时：
递归的深度等于n的质因数总个数，质因数个数最多的情况就是n所有质因子都是2，最多有log2(n)个，递归最多执行log2(n)次，每次额外操作都是O(1)，因此仅递归部分的时间复杂度为O(log n)。

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