质因数分解算法的复杂性

Question

我刚刚学习了如何使用这个算法来找到一个数字的质因数。该算法基本上是这样运作的：

void printPrimeFactors(N) {

  while N is even
    print 2 as prime factor
    N = N/2

  // At this point N is odd
  for all the ODDS i from 3 to sqrt(N)
    while N is divisible by i
      print i as prime factor
      N = N / i

  if N hasn't been divided by anything (i.e. it's still N)
    N is prime

  }

一切都很清楚，但我不确定如何计算上述程序的大O复杂度。

作为最昂贵的操作（我想），除法可能是最坏情况下最多有log(N)次，但我并不完全确定。

- Dean

---

我认为可除性检查是主要因素，当N为质数时最糟糕。这意味着你需要进行sqrt(N)次检查，而所有的检查结果都是false。 - biziclop

很好的观点，现在你让我想起来了。O(sqrt(N))似乎比我想象的更合理。 - Dean

@biziclop，这个特定算法的时间复杂度为O(sqrt(N))。然而，这个算法远非最优解。例如，在ODDS i的主循环中，每次成功迭代后，您可以将上限从sqrt(N)减少到sqrt(N /已知因子的乘积)。在实现之前，我建议您研究“筛法”和相关算法。 - Michael

@Michael 你说得对，我假设随着 N 的更新，上限也会下降。当然，即使你仔细调整你的上限并跳过已知的合数（将算法转化为基本的 Erathosthenes 筛法），该算法仍远非最优。 - biziclop

Answer 1

您可以按照以下步骤进行操作。首先，我们只关注当N非常大时应用程序的行为。在这种情况下，我们可以简化很多内容：如果两个部分具有不同的渐近性能，则只需选择表现最差的那个。

第一个while循环最多可以循环m次，其中m是使2^m >= N的最小整数。因此，它最坏情况下会循环log₂N次--这意味着它的效率为O(log N)。请注意，当N足够大时，对数类型是无关紧要的。 for循环运行O(sqrtN)次。在规模上，这比logN大得多，因此我们可以放弃log。

最后，我们需要评估循环内的while。由于此while循环仅在除数中执行，因此其大O等于它们的数量。经过一点思考，我们可以看到，最坏情况下，while将循环log₃N次，因为3是最小可能的除数。

因此，while循环仅执行O(log N)次，但外部for会执行O(sqrt N)次（而且通常不运行while循环，因为当前数字不能被整除）。

总之，最耗时的部分是for循环，这将使算法以O(sqrt N)进行。

- Sklivvz

---

好的解释。小细节：分割次数是 O(sqrt(N))，但由于在大于O(1)的大数字上进行除法操作，算法的运行时间复杂度更差。 - le_m