基于因数的复杂度分析：为何最大因数数量与√n相关？

给定代码 #

for(int i = 1; i < len; i++) {
    if(n % i == 0 && someFunc()) {
        // do something;
    }
}

已知条件：

• someFunc() 的时间复杂度为 O(n)
• 仅当 i 是 n 的因数时，才会触发 someFunc() 调用

疑问：

1. 一个数最多能有多少个因数？
2. 为什么这段代码的最大时间复杂度是 O(n*√n)，且最大因数数量是√n级别的？

解答 #

1. 因数数量的上限 #

一个数的因数数量由它的质因数分解决定：如果 n = p₁^a₁ * p₂^a₂ * ... * p_k^a_k（p为质数，a为对应指数），那因数总数是 (a₁+1)*(a₂+1)*...*(a_k+1)。但从量级上看，任何数n的因数数量都不会超过2√n。

原因很直观：因数都是成对存在的——如果i是n的因数，那n/i也必然是n的因数。每一对里至少有一个数≤√n，所以总因数数最多是2√n（当n是完全平方数时，√n会单独算一个，但不影响整体量级）。

2. 时间复杂度推导 #

回到代码：

• 循环遍历到len（合理推测这里是遍历到n，否则逻辑不完整），但只有因数i会触发someFunc()。
• 因数的最大数量是**O(√n)**级，每次someFunc()耗时O(n)，所以总时间就是O(n * √n)。

举个实际例子：当n是完全平方数k²时，它的因数数量大概是2k（也就是2√n），此时总执行时间就是2√n * n，量级上就是O(n√n)。

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