为何数字各位求和的时间复杂度是O(logN)而非O(N)？

先把你提到的代码贴出来：

int sumDigits(int n) { 
    int sum = 0; 
    while (n > 0) { 
        sum += n % 10; 
        n /= 10; 
    } 
    return sum; 
}

你对代码执行逻辑的理解完全没问题——每次取个位累加，再砍掉个位，循环次数就是数字的位数。那咱们来拆解你纠结的两个问题：

疑问1：为何要令n=10^d？ #

其实这是用数学方式把「数字位数」和「数值大小」的关系量化出来，属于一种简化的推导思路。咱们换个接地气的角度看：

• 1位数（d=1）的最大值是9，小于10^1=10
• 2位数（d=2）的最大值是99，小于10^2=100
• 3位数（d=3）的最大值是999，小于10^3=1000
  以此类推，任何d位数的数值n，都满足 10^(d-1) ≤ n <10^d。如果对这个不等式两边取以10为底的对数，会得到：
  d-1 ≤ log₁₀n <d
  这就直接把位数d和log₁₀n绑定了——d等于floor(log₁₀n)+1，本质上d和logn是线性相关的。

拿n=10^d举例，只是为了用最直观的方式把对应关系摆出来：当n刚好是10的d次方时，log₁₀n=d，一眼就能看出来「位数=logn」，是个简化的极端例子，不是说所有输入n都是10的幂。

疑问2：如何得出时间复杂度是O(logN)而非O(N)？ #

首先得明确：时间复杂度里的N指的是输入的数值本身，不是它的位数。

如果是O(N)的话，意味着循环次数会随着N的增大线性增长——比如N从10变到100，循环次数要从10次涨到100次，但实际咱们的代码里：

• N=10（2位数）循环2次
• N=100（3位数）循环3次
• N=1000（4位数）循环4次

循环次数的增长速度是对数级的，和logN的增长节奏完全匹配。再举个更夸张的例子：

• N=10^3=1000，循环3次，log₁₀N=3
• N=10^6=1000000，循环6次，log₁₀N=6
• N=10^9=1000000000，循环9次，log₁₀N=9

你看，N翻了1000倍（从10^3到106），循环次数只翻了2倍；N再翻1000倍到10^{9，循环次数也只涨了50%。这种慢到离谱的增长速度就是对数级的，对应时间复杂度O(logN)。而如果是O(N)的话，N从10}3到10^6，循环次数要从1000次涨到1000000次，那完全是天差地别的增长节奏。

总结一下：代码的循环次数等于数字的位数d，而d和logN是线性相关的，所以时间复杂度是O(logN)，而非O(N)。

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