Java算法时间复杂度分析：digPow函数的复杂度判定

先贴出代码：

public static int digPow(int n, int p) {
  int powCounter = p;
  int sum = 0;
  char[] digits = (""+n).toCharArray();

  for (char digit : digits) {
    sum += Math.pow(Character.getNumericValue(digit), powCounter);
    powCounter++;
  }

  if (sum % n == 0) return sum / n;
  else return -1;
}

核心结论 #

这个算法的时间复杂度是O(log₁₀n)，也可简化写成O(log n)，既不是你担心的更高复杂度，也不是线性O(n)——这里容易混淆变量名n和循环次数的关系，实际循环次数和n的位数相关，而非n的数值大小。

具体分析 #

1. 循环次数的本质：
   循环遍历的是n的每一位数字，循环次数等于n的位数。比如n=123时循环3次，n=12345时循环5次。而一个数n的位数是floor(log₁₀n) + 1，和n的数值是对数关系，所以循环次数是O(log n)级别。

2. 循环内操作的时间：
   循环里调用的Math.pow，其底数是0-9的单个数字（固定范围），不管指数powCounter怎么增长，这个幂运算的时间开销都是常数级——要么是底层快速计算，要么是小数值的查表操作，不会随n的规模变大而线性增加。所以每次循环的操作都是O(1)。

3. 其他操作的影响：
   把n转成字符数组的操作，时间也和n的位数成正比，也就是O(log n)，和循环的复杂度一致。最后的取模、除法操作都是常数级O(1)。

综上，整个函数的时间复杂度由循环次数主导，是O(log n)。

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