质因数算法的复杂度

Question

我刚刚研究了如何使用 this 算法找到一个数的质因数，基本上是这样工作的：

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

  }

一切都清楚了，但是我不确定如何计算上面程序的 big-O 复杂度。

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

Answer 1

您可以这样进行。首先，我们只对 N 非常大时应用程序的行为感兴趣。在那种情况下，我们可以简化很多：如果两个部分具有不同的渐近性能，我们只需要表现最差的那个。

第一个while最多可以循环m次，其中m是最小的整数，所以2^m>=N。因此，在最坏的情况下，它会循环 log₂N 次——这意味着它的执行时间为 O(log N)。请注意，当 N 足够大时，日志类型无关紧要。

for 循环运行s O(sqrt N) 次。在规模上，这比日志 N 大得多，因此我们可以删除日志。

最后，我们需要计算循环内的while。由于此 while 循环仅针对除数执行，因此它将有一个等于除数的大 O。稍加思考我们可以看到，在最坏的情况下，while 将循环 log₃N 次，因为 3 是可能的最小除数。

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

总而言之，花费时间最长的部分是 for 循环，这将使算法的运行时间复杂度为 O(sqrtN)。

质因数算法的复杂度

Complexity of prime factor algorithm

language-agnostic

algorithm

complexity-theory