这个朴素的质因数分解算法有多快？
How fast is this naive prime factorization algorithm?
我想弄清楚这段代码的复杂性：
prime_factorize(N) {
for (int i = 2; i <= N; i++) {
while (N % i == 0) {
print i
N = N / i
}
}
}
这实际上不是编程语言 -- 它只是伪代码。
我知道伪代码在做什么。它除掉了 2、3 等的所有因数。我也知道代码可以优化到只达到 sqrt(N)，但我想在发布代码时弄清楚代码的运行时间.
虽然说运行时是二次的很诱人，但我很确定这是错误的。我之所以认为它是错误的，是因为我知道素数筛算法的运行时间是O(nloglogn)，它有点像这个算法。
谁能帮我分析一下这个算法？
很容易看出该算法在最坏情况下的运行时间为 O(n)。
你只需要考虑n是质数的情况，那么i会一直迭代到N。
如果 N 不是质数，也会发生同样的事情。以 N = 2 * 53 为例。需要 53 次迭代 = O(N/2) = O(N).
我想弄清楚这段代码的复杂性：
prime_factorize(N) {
for (int i = 2; i <= N; i++) {
while (N % i == 0) {
print i
N = N / i
}
}
}
这实际上不是编程语言 -- 它只是伪代码。
我知道伪代码在做什么。它除掉了 2、3 等的所有因数。我也知道代码可以优化到只达到 sqrt(N)，但我想在发布代码时弄清楚代码的运行时间.
虽然说运行时是二次的很诱人，但我很确定这是错误的。我之所以认为它是错误的，是因为我知道素数筛算法的运行时间是O(nloglogn)，它有点像这个算法。
谁能帮我分析一下这个算法？
很容易看出该算法在最坏情况下的运行时间为 O(n)。
你只需要考虑n是质数的情况，那么i会一直迭代到N。
如果 N 不是质数，也会发生同样的事情。以 N = 2 * 53 为例。需要 53 次迭代 = O(N/2) = O(N).