素因子算法的复杂性 [英] Complexity of prime factor algorithm

问题描述

我刚刚学习了如何用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复杂度。

作为最昂贵的运算(我想)，我会说最坏的情况可能是最多有对数(N)个除法，但我不能完全确定这一点。

推荐答案

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

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

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

最后，我们需要计算循环内的while。因为这个While循环只对除数执行，所以它将有一个等于它们的数字的大O。稍微想一想，我们可以看到，在最坏的情况下，while将对数N循环3次，因为3是可能的最小除数。

因此，While循环只执行O(logN)次，但外部for执行O(SQRTN)次(通常情况下，While循环不会运行，因为当前的数字不会相除)。

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

这篇关于素因子算法的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！