for 循环内递归分解函数的时间复杂度

Question

这是我在伪代码中的算法：它的作用是返回一个素数列表，给出数字 n 的因式分解。例如，75 = 3 * 5 * 5

public static ArrayList<Integer> FACTORISATION(int n) {
if (PRIME(n)) {
// return a one-element array
return new ArrayList<Integer>(Arrays.asList(n));
} else {
// find a prime divisor, p
for (int i = 2; i < Math.sqrt(n); i++) {
if (n % i == 0) {
ArrayList<Integer> newList = new ArrayList<>();
newList.add(i);
newList.addAll(FACTORISATION(n/i));
return newList;
}
}
}
return new ArrayList<>();
}

据我说，时间复杂度可以计算为：-

T(n) = 2 + T(n-1/p) + T(n-2/p) +...
T(n) = nT(n-1/p)
T(n) = O(n!)

PRIME(n)方法的复杂性为O(n)

这是对的吗？

Answer 1

这有点复杂。首先，请更正代码中的错误，它应该是i <= Math.sqrt(n);而不是i < Math.sqrt(n);。

让我们从整数的唯一表示开始，它是其素数除数的幂乘积：

n = p 1 a 1 p 2 a₂p3^a₃...噗��

(例如，120 = 2^{3 31}5¹)。代码中的循环for为输入n执行多少次(不包括递归子调用)？正好i-1次，其中i是n的最小素数。这是因为当第一次找到这样的i时，循环终止(return newList;语句)。如果n本身是素数，则根本不会执行for循环，因为if (PRIME(n))将返回 true。

对于哪些输入参数FACTORISATION(int n)调用(递归)？注意，它会被称为 n，然后是

不适用₁，

不适用₁²，

..

不适用₁^A₁，

不适用₁^A₁P₂，

n/p1^a₁p 2²，

..

n/p 1 a^₁p 2^a₂，

..

n/p 1 a 1 p 2 a^₂p 3^a₃...P_K，

..

n/p 1 a 1 p 2 a^₂p 3^a₃...P K^A_K-1。

这是最困难的部分 - 如果你理解了这一点，你就完成了:)现在只需总结一下测试PRIME(n)的运行时间和执行循环for运行时间。后者的总贡献为 (p 1 -1)a 1 + (p 2 -₁)a₂+ ..+ (pk - 1)a_k，而第一部分贡献 n + n/p₁+ n/p 1 2 + ... + n/p 1 a^₁p 2 a^₂p 3^a₃...P K^A_K-1。如果不认真研究数论，就不可能评估这个和的渐近复杂度，但它比O(n!)要好得多(有关除数和的上限，请参见此处)。