algorithm - 这个 Prime Factor 函数的运行时间？

Question

我写了这个质因数分解函数，谁能给我解释一下运行时间？这对我来说似乎很快，因为它不断地将数字分解为素数，而无需检查因子是否为素数，并且在最坏的情况下从 2 运行到数字。

我知道目前还没有函数可以在多项式时间内分解素数。此外，运行时间如何渐进地与大素数因式分解相关？

function getPrimeFactors(num) {
    var factors = [];
    for (var i = 2; i <= num; i++) {
        if (num % i === 0) {
            num = num / i;
            factors.push(i);
            i--;
        }
    }
    return factors;
}

Answer 1

在您的示例中，如果 num 是质数，那么它将恰好需要 num - 1 步。这意味着该算法的运行时间为 O(num)(其中 O 代表悲观 情况)。但是对于对数字进行运算的算法，事情会变得有点棘手(感谢您注意到 thegreatcontini 和 Chris)!我们总是将复杂性描述为输入大小的函数。在这种情况下，输入是一个数字 num，它用 log(num) 位表示。所以输入大小是log(num)。因为 num = 2 ^ (log(num)) 那么你的算法很复杂 O(2^k) 其中 k = log(num) - 输入的大小。

这就是使这个问题变得困难的原因 - 输入非常非常小，num 中的任何多项式都会导致指数算法...

旁注 @rici 是对的，您只需要检查 sqrt(num)，从而轻松将运行时间减少到 O(sqrt(num)) 或更准确地说 O(sqrt(2) ^ k)。